Practice Special Array II
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
Problem Statement
For every inclusive range [left, right] in queries, decide whether neighboring values throughout nums[left..right] alternate between odd and even. Return one boolean per query. A range containing a single value qualifies because it has no adjacent pair. Approach: Build a prefix count of edges whose two endpoints have equal parity. A query is valid when its interval contains zero such edges. With bad[i] counting failing edges up to i, test bad[right] - bad[left] == 0. Preprocessing takes O(n), each query O(1), and storage O(n).
Source: Special Array II on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
nums = [2,5,7,4], queries = [[0,1],[0,3],[2,3],[1,1]]
[true,false,true,true]
The full range fails at the adjacent odd values 5 and 7. The other ranges alternate parity or contain one value.
Constraints
How to solve Special Array II
Original notes for interview preparation, written for this problem. Reviewed .
Key insight
A range alternates parity exactly when none of its adjacent pairs share a parity, and adjacency is a fixed property of the array independent of the query. A prefix count of offending pairs makes each query a constant-time subtraction.
Why brute force is not enough
Scanning each query's range and comparing neighbors is O(right - left) per query; with nums.length and queries.length both up to 10^5, long ranges push this toward 10^10 comparisons.
Approach
- Call the pair (i - 1, i) bad when nums[i - 1] and nums[i] have the same parity, and record at each position i the number of bad pairs whose right endpoint is at most i, with 0 at position 0.
- Build this running count in one pass, incrementing when the current element and its predecessor are both even or both odd; the value at i counts bad pairs fully inside the prefix ending at i.
- For a query [left, right], the bad pairs inside it have right endpoints in left + 1 through right, so their count is prefix[right] minus prefix[left].
- Answer true when the difference is zero; a range with left equal to right has no interior pair and is automatically true.
Walkthrough of Example 1
nums = [2,5,7,4], queries = [[0,1],[0,3],[2,3],[1,1]] → [true,false,true,true]
- Parities of [2, 5, 7, 4] are even, odd, odd, even; the pairs (2,5) and (7,4) differ while (5,7) match.
- Prefix bad counts are 0, 0, 1, 1 at indices 0 through 3.
- Query [0,1]: 0 - 0 = 0, true. Query [0,3]: 1 - 0 = 1, false.
- Query [2,3]: 1 - 1 = 0, true. Query [1,1]: 0 - 0 = 0, true.
- The result is [true, false, true, true].
Time and space
Time O(n + q) · Space O(n). Building the prefix over n elements is linear and each of the q queries is one subtraction; the prefix array is the only linear storage beyond the answers.
Interview pitfalls
- Subtracting the prefix at left - 1 instead of at left, which counts the pair ending at left even though it lies outside the range.
- Treating a single-element range as invalid; with no adjacent pair it must be true.
- Comparing remainders in a language where negative numbers give negative remainders; values here are positive, but a bitwise AND with 1 avoids the habit.
- Storing good pairs and comparing against range length minus one, which works but invites off-by-one errors.
Follow-up questions interviewers ask
- How would you support point updates to nums between queries, and what replaces the static prefix array?
- Can you solve it with run identifiers, labeling maximal alternating runs and comparing labels at both ends?
- How would you extend the check to a repeating cycle of three residues modulo 3?
Further reading on the technique: Prefix sum
Related LeetCode Problems
Practice more problems similar to Special Array II.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.