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.

Examples

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

Solution

Video explanation

Here is the video explaining this method in detail. Please check it out:

Method 1 - Naive - Naively check the parity for each query

Here is the approach:

  • Iterate through each query.
  • For each query, check the subarray from index fromi to toi to ensure all adjacent elements have different parity.
  • Store the result (boolean) in the answer array.

Code

Java
class Solution {
    public boolean[] isArraySpecial(int[] nums, int[][] queries) {
        boolean[] ans = new boolean[queries.length];
        int i = 0;
        for (int[] q : queries) {
            int from = q[0];
            int to = q[1];
            boolean isSpecial = true;
            for (int i = from; i < to; i++) {
                if ((nums[i] % 2) == (nums[i + 1] % 2)) {
                    isSpecial = false;
                    break;
                }
            }
            ans[i++] = isSpecial;
        }
        return ans;
    }
}
Python
class Solution:
    def is_array_special(self, nums: List[int], queries: List[List[int]]) -> List[bool]:
        ans: List[bool] = []
        for q in queries:
            from_i: int = q[0]
            to_i: int = q[1]
            is_special: bool = True
            for i in range(from_i, to_i):
                if (nums[i] % 2) == (nums[i + 1] % 2):
                    is_special = False
                    break
            ans.append(is_special)
        return ans

Complexity

  • ⏰ Time complexity: O(m * a), where m is the number of queries and a is the average length of the subarrays, and in worst case a = n.
  • 🧺 Space complexity: O(m) for storing the output list.

Method 2 - Using prefix sum

We need to create a prefix sum OR prefix count array starting from zero, where we increment the value each time a pair of numbers with the same parity is encountered. At the end, if the start and end indices share the same value, it implies the subarray contains no pairs of identical parity. Conversely, if the values differ, a pair with the same parity must exist within that range. Here is the approach:

  • Create a pre-processed array starting with an initial value of zero.
  • Iterate through the nums array and update the converted vector. Increment the value (j) if the current element’s parity matches that of the previous element.
  • After building the converted vector, process each query. Check if the start and end indices in the converted vector are equal; if so, append true to the answer list. Otherwise, append false. An equal start and end index indicates no pairs with the same parity within the range. If there were pairs with the same parity, the end index’s value would be greater than the start index’s value.

Code

Java
class Solution {
    public boolean[] isArraySpecial(int[] nums, int[][] queries) {
        int n = nums.length;
        int[] prefixSum = new int[n];
        prefixSum[0] = 0;
        
        int j = 0;
        for (int i = 1; i < n; i++) {
            if ((nums[i] % 2) == (nums[i - 1] % 2)) {
                j++;
            }
            prefixSum[i] = j;
        }
        
        boolean[] ans = new boolean[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int from = queries[i][0];
            int to = queries[i][1];
            ans[i] = (prefixSum[from] == prefixSum[to]);
        }
        
        return ans;
    }
}
Python
 class Solution:
     def is_array_special(self, nums: List[int], queries: List[List[int]]) -> List[bool]:
         n = len(nums)
         prefix_sum = [0] * n
         
         j = 0
         for i in range(1, n):
             if (nums[i] % 2) == (nums[i - 1] % 2):
                 j += 1
             prefix_sum[i] = j
         
         ans = [False] * len(queries)
         for i in range(len(queries)):
             from_i = queries[i][0]
             to_i = queries[i][1]
             ans[i] = (prefix_sum[from_i] == prefix_sum[to_i])
         
         return ans

Complexity

  • ⏰ Time complexity: O(n + m) where it takes O(n) for preprocessing step
  • 🧺 Space complexity: O(n + m) for storing the prefix sum and output list.