Special Array II

medium array prefix sum parity

Problem

An array is special if every pair of adjacent elements contains two numbers of different parity (one odd, one even). Given nums and a list of queries [from, to], return a boolean for each query that is true when the subarray nums[from..to] is special.

The trick: precompute a prefix array bad where bad[i] counts how many adjacent pairs up to index i share the same parity (a “break”). A subarray [lo, hi] is special exactly when it contains no break, i.e. bad[hi] − bad[lo] == 0.

Inputnums = [3,4,1,2,6], queries = [[0,4]]

Output[false]

Parities are O,E,O,E,E. The pair (2, 6) is even/even — a break inside [0,4] — so the subarray is not special.

nums (comma-separated)

queries (from:to, comma-separated)

def isArraySpecial(nums, queries):
    n = len(nums)
    bad = [0] * n                       # bad[i]: same-parity breaks up to index i
    for i in range(1, n):
        same = (nums[i] % 2) == (nums[i - 1] % 2)
        bad[i] = bad[i - 1] + (1 if same else 0)
    answer = []
    for lo, hi in queries:
        # special iff no break lies in (lo, hi]
        answer.append(bad[hi] - bad[lo] == 0)
    return answer

function isArraySpecial(nums, queries) {
  const n = nums.length;
  const bad = new Array(n).fill(0);     // bad[i]: same-parity breaks up to index i
  for (let i = 1; i < n; i++) {
    const same = (nums[i] & 1) === (nums[i - 1] & 1);
    bad[i] = bad[i - 1] + (same ? 1 : 0);
  }
  const answer = [];
  for (const [lo, hi] of queries) {
    // special iff no break lies in (lo, hi]
    answer.push(bad[hi] - bad[lo] === 0);
  }
  return answer;
}

boolean[] isArraySpecial(int[] nums, int[][] queries) {
    int n = nums.length;
    int[] bad = new int[n];             // bad[i]: same-parity breaks up to index i
    for (int i = 1; i < n; i++) {
        boolean same = (nums[i] & 1) == (nums[i - 1] & 1);
        bad[i] = bad[i - 1] + (same ? 1 : 0);
    }
    boolean[] answer = new boolean[queries.length];
    for (int q = 0; q < queries.length; q++) {
        int lo = queries[q][0], hi = queries[q][1];
        // special iff no break lies in (lo, hi]
        answer[q] = bad[hi] - bad[lo] == 0;
    }
    return answer;
}

vector<bool> isArraySpecial(vector<int>& nums, vector<vector<int>>& queries) {
    int n = nums.size();
    vector<int> bad(n, 0);              // bad[i]: same-parity breaks up to index i
    for (int i = 1; i < n; i++) {
        bool same = (nums[i] & 1) == (nums[i - 1] & 1);
        bad[i] = bad[i - 1] + (same ? 1 : 0);
    }
    vector<bool> answer;
    for (auto& qr : queries) {
        int lo = qr[0], hi = qr[1];
        // special iff no break lies in (lo, hi]
        answer.push_back(bad[hi] - bad[lo] == 0);
    }
    return answer;
}

Explanation

The naive approach — scanning every subarray per query — costs O(n) per query and is too slow when both nums and queries can hold 10⁵ elements. We need each query answered in constant time after one linear pass.

Notice the property is purely local: a subarray fails to be special the moment two neighbours share parity. Call such a neighbouring pair a break. A subarray is special if and only if it contains zero breaks.

So we build a prefix sum of breaks. bad[i] stores how many breaks occur among the adjacencies (0,1), (1,2), …, (i-1,i). We compute it in one left-to-right scan: bad[i] = bad[i-1] + 1 when nums[i] and nums[i-1] have the same parity, otherwise it carries the previous value forward.

For a query [lo, hi], the breaks strictly inside that window are exactly the adjacencies (lo, lo+1) … (hi-1, hi), which number bad[hi] − bad[lo]. If that difference is 0 there is no break, so the subarray is special; otherwise it is not. (Single-element queries where lo == hi give 0 and are trivially special.)

Example: nums = [4,3,1,6] has parities E,O,O,E with a single break at index 2 (3 and 1 are both odd), giving bad = [0,0,1,1]. Query [0,2] yields 1 − 0 = 1 → not special; query [2,3] yields 1 − 1 = 0 → special.

Time: O(n + q) Space: O(n)