# 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:

1. The subarray is [4,3,1]. 3 and 1 are both odd. So the answer to this query is false.
2. 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 is true.

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.

• class Solution {
public boolean[] isArraySpecial(int[] nums, int[][] queries) {
int n = nums.length;
int[] d = new int[n];
for (int i = 1; i < n; ++i) {
if (nums[i] % 2 != nums[i - 1] % 2) {
d[i] = d[i - 1];
} else {
d[i] = i;
}
}
int m = queries.length;
boolean[] ans = new boolean[m];
for (int i = 0; i < m; ++i) {
ans[i] = d[queries[i][1]] <= queries[i][0];
}
return ans;
}
}

• class Solution {
public:
vector<bool> isArraySpecial(vector<int>& nums, vector<vector<int>>& queries) {
int n = nums.size();
vector<int> d(n);
iota(d.begin(), d.end(), 0);
for (int i = 1; i < n; ++i) {
if (nums[i] % 2 != nums[i - 1] % 2) {
d[i] = d[i - 1];
}
}
vector<bool> ans;
for (auto& q : queries) {
ans.push_back(d[q[1]] <= q[0]);
}
return ans;
}
};

• class Solution:
def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:
n = len(nums)
d = list(range(n))
for i in range(1, n):
if nums[i] % 2 != nums[i - 1] % 2:
d[i] = d[i - 1]
return [d[t] <= f for f, t in queries]


• func isArraySpecial(nums []int, queries [][]int) (ans []bool) {
n := len(nums)
d := make([]int, n)
for i := range d {
d[i] = i
}
for i := 1; i < len(nums); i++ {
if nums[i]%2 != nums[i-1]%2 {
d[i] = d[i-1]
}
}
for _, q := range queries {
ans = append(ans, d[q[1]] <= q[0])
}
return
}

• function isArraySpecial(nums: number[], queries: number[][]): boolean[] {
const n = nums.length;
const d: number[] = Array.from({ length: n }, (_, i) => i);
for (let i = 1; i < n; ++i) {
if (nums[i] % 2 !== nums[i - 1] % 2) {
d[i] = d[i - 1];
}
}
return queries.map(([from, to]) => d[to] <= from);
}