3152. Special Array II
Description
An array is considered special if every pair of its adjacent elements contains two numbers with different parity.
You are given an array of integer nums
and a 2D integer matrix queries
, where for queries[i] = [fromi, toi]
your task is to check that subarray nums[fromi..toi]
is special or not.
Return an array of booleans answer
such that answer[i]
is true
if nums[fromi..toi]
is special.
Example 1:
Input: nums = [3,4,1,2,6], queries = [[0,4]]
Output: [false]
Explanation:
The subarray is [3,4,1,2,6]
. 2 and 6 are both even.
Example 2:
Input: nums = [4,3,1,6], queries = [[0,2],[2,3]]
Output: [false,true]
Explanation:
- The subarray is
[4,3,1]
. 3 and 1 are both odd. So the answer to this query isfalse
. - The subarray is
[1,6]
. There is only one pair:(1,6)
and it contains numbers with different parity. So the answer to this query istrue
.
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 105
1 <= queries.length <= 105
queries[i].length == 2
0 <= queries[i][0] <= queries[i][1] <= nums.length - 1
Solutions
Solution 1: Record the Leftmost Special Array Position for Each Position
We can define an array $d$ to record the leftmost special array position for each position, initially $d[i] = i$. Then we traverse the array $nums$ from left to right. If $nums[i]$ and $nums[i - 1]$ have different parities, then $d[i] = d[i - 1]$.
Finally, we traverse each query and check whether $d[to] <= from$ holds.
The time complexity is $O(n)$ and the space complexity is $O(n)$, where $n$ is the length of the array.
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 |
|