# Special Array II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/special-array-ii)
Canonical: https://scaleengineer.com/dsa/problems/special-array-ii
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [National Payments Corporation of India](https://scaleengineer.com/companies/national-payments-corporation-of-india)
---
## Problem
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`

# Approaches
## Brute Force Iteration
This approach directly translates the problem statement into code. For each query, it iterates through the specified subarray and checks if every adjacent pair of elements has different parity. It is the most straightforward but least efficient method.
**Time:** O(Q * N), where `Q` is the number of queries and `N` is the length of `nums`. In the worst case, each query could span the entire array, leading to `Q * N` operations. · **Space:** O(Q) to store the output array. If the output array is not considered part of the space complexity, it is O(1).
**Pros:** Simple to understand and implement.; Requires no extra space besides the output array, making it memory efficient.
**Cons:** Highly inefficient for large inputs due to its quadratic time complexity in the worst case.; Will result in a 'Time Limit Exceeded' (TLE) error on competitive programming platforms for the given constraints.; Repeatedly re-computes results for overlapping subarrays, which is redundant work.
### Explanation
We can solve this problem by iterating through each query one by one. For a given query `[from, to]`, we check every adjacent pair of numbers in the subarray `nums[from...to]`. 

A subarray is special if for all `i` from `from` to `to - 1`, the parity of `nums[i]` is different from the parity of `nums[i+1]`. We can check the parity of a number using the modulo operator (`number % 2`). If `nums[i] % 2` is equal to `nums[i+1] % 2`, their parities are the same, and the subarray is not special. We can then immediately stop checking for this query and move to the next one.

If we iterate through all adjacent pairs in the subarray and don't find any with the same parity, the subarray is special. A subarray with a single element (`from == to`) is always considered special.

```java
class Solution {
    public boolean[] isSpecialArray(int[] nums, int[][] queries) {
        boolean[] answer = new boolean[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int from = queries[i][0];
            int to = queries[i][1];
            
            if (from == to) {
                answer[i] = true;
                continue;
            }
            
            // Assume the subarray is special initially
            boolean isSpecial = true;
            // Check all adjacent pairs in the subarray
            for (int j = from; j < to; j++) {
                if ((nums[j] % 2) == (nums[j + 1] % 2)) {
                    isSpecial = false;
                    break; // Found a non-special pair, no need to check further
                }
            }
            answer[i] = isSpecial;
        }
        return answer;
    }
}
```
### Algorithm
- 1. Initialize a boolean array `answer` with the same size as `queries`.
- 2. Loop through each query `[from, to]` from the `queries` matrix.
- 3. For each query, handle the base case where `from == to`; the subarray is always special.
- 4. If `from != to`, loop from index `j = from` to `to - 1`.
- 5. Inside the inner loop, check if `nums[j]` and `nums[j+1]` have the same parity using the modulo operator: `(nums[j] % 2) == (nums[j+1] % 2)`.
- 6. If they have the same parity, the subarray is not special. Mark the result for the current query as `false` and break the inner loop to proceed to the next query.
- 7. If the inner loop completes without finding any pair with the same parity, the subarray is special. Mark the result as `true`.
- 8. After processing all queries, return the `answer` array.

## Prefix Sum on "Bad Pairs"
This is an optimized approach that avoids re-computation by preprocessing the input array. We can identify all adjacent pairs with the same parity (let's call them "bad pairs") and use a prefix sum array to count them. A query for a subarray `[from, to]` can then be answered in constant time by checking if there are any "bad pairs" within that range.
**Time:** O(N + Q), where `N` is the length of `nums` and `Q` is the number of queries. `O(N)` for preprocessing and `O(Q)` for answering all queries. · **Space:** O(N + Q). `O(N)` for the prefix sum array and `O(Q)` for the output array. If the output array is not considered, the space complexity is `O(N)`.
**Pros:** Highly efficient, with a linear time complexity overall.; Answers each query in constant time after an initial linear-time preprocessing step.; Perfectly suited for problems with a large number of range queries on a static array.
**Cons:** Requires additional space proportional to the size of the input array `nums` for the prefix sum array.
### Explanation
A subarray `nums[from...to]` is special if and only if there are no indices `i` (where `from <= i < to`) such that `nums[i]` and `nums[i+1]` have the same parity.

We can precompute an array, let's call it `prefixBadCount`, of size `n` (length of `nums`). `prefixBadCount[i]` will store the total number of "bad pairs" in the prefix of the array `nums[0...i]`. A "bad pair" is an adjacent pair of elements with the same parity.

The `prefixBadCount` array is built as follows:
- `prefixBadCount[0] = 0`.
- For `i` from 1 to `n-1`, `prefixBadCount[i] = prefixBadCount[i-1]`. If the pair `(nums[i-1], nums[i])` is a bad pair (i.e., `nums[i-1] % 2 == nums[i] % 2`), we increment `prefixBadCount[i]` by 1.

After building this prefix sum array, we can answer any query `[from, to]` in O(1) time. The number of bad pairs in the subarray `nums[from...to]` corresponds to the bad pairs at indices `(from, from+1), (from+1, from+2), ..., (to-1, to)`. The total count of these bad pairs can be calculated as `prefixBadCount[to] - prefixBadCount[from]`. If this difference is 0, it means there are no bad pairs in the subarray, so it's special. Otherwise, it's not.

```java
class Solution {
    public boolean[] isSpecialArray(int[] nums, int[][] queries) {
        int n = nums.length;
        int[] prefixBadCount = new int[n];
        
        // prefixBadCount[i] stores the number of adjacent pairs with the same parity
        // in the prefix nums[0...i]. The check is for the pair (nums[i-1], nums[i]).
        for (int i = 1; i < n; i++) {
            prefixBadCount[i] = prefixBadCount[i - 1];
            if ((nums[i] % 2) == (nums[i - 1] % 2)) {
                prefixBadCount[i]++;
            }
        }
        
        int q = queries.length;
        boolean[] answer = new boolean[q];
        for (int i = 0; i < q; i++) {
            int from = queries[i][0];
            int to = queries[i][1];
            
            if (from == to) {
                answer[i] = true;
                continue;
            }
            
            // The number of bad pairs in the subarray nums[from...to] is the
            // number of bad pairs up to index 'to' minus the number of bad pairs
            // up to index 'from'.
            int badPairsInSubarray = prefixBadCount[to] - prefixBadCount[from];
            
            answer[i] = (badPairsInSubarray == 0);
        }
        
        return answer;
    }
}
```
### Algorithm
- 1. Create a prefix sum array `prefixBadCount` of size `n` (length of `nums`).
- 2. Initialize `prefixBadCount[0] = 0`.
- 3. Iterate from `i = 1` to `n-1`. For each `i`, set `prefixBadCount[i] = prefixBadCount[i-1]`. If `nums[i]` and `nums[i-1]` have the same parity, increment `prefixBadCount[i]`.
- 4. Initialize an answer array `answer` of size `q` (number of queries).
- 5. Iterate through each query `[from, to]`.
- 6. For each query, calculate the number of "bad pairs" in the subarray `nums[from...to]` as `prefixBadCount[to] - prefixBadCount[from]`.
- 7. If the result is 0, the subarray is special, so set `answer[i] = true`. Otherwise, set `answer[i] = false`.
- 8. Return the `answer` array.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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]

```