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:
[4,3,1]. 3 and 1 are both odd. So the answer to this query is false.[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 <= 1051 <= nums[i] <= 1051 <= queries.length <= 105queries[i].length == 20 <= queries[i][0] <= queries[i][1] <= nums.length - 1Problem Overview: You receive an integer array nums and multiple queries [l, r]. A subarray is considered special if every pair of adjacent elements has different parity (one even, one odd). For each query, determine whether the subarray from index l to r satisfies this condition.
Approach 1: Brute Force Check per Query (O(q * n) time, O(1) space)
The most direct strategy is to evaluate every query independently. For a query [l, r], iterate from l to r-1 and check whether nums[i] % 2 equals nums[i+1] % 2. If two adjacent numbers share the same parity, the subarray is not special. This approach uses simple iteration and parity checks with constant extra memory. The downside is repeated work across overlapping queries, which pushes the worst‑case runtime to O(q * n). It works for small inputs but struggles when both the array length and query count are large.
Approach 2: Prefix Parity Difference Array (O(n + q) time, O(n) space)
An optimized approach precomputes where the array violates the special condition. Build a difference array where bad[i] = 1 if nums[i] and nums[i-1] have the same parity, otherwise 0. Next, compute a prefix sum over this array so you can quickly count parity violations in any range. For a query [l, r], check the prefix sum between l+1 and r. If the sum is 0, no adjacent elements share the same parity and the subarray is special. This transforms repeated scans into constant‑time checks using a prefix sum structure.
The key insight is that the property of being special depends only on adjacent pairs. Once those violations are precomputed, every query becomes a quick range check. This is a common pattern in array preprocessing problems: convert repeated validations into prefix statistics that answer queries instantly. While the problem lists binary search among related topics, the efficient solution mainly relies on prefix aggregation.
Recommended for interviews: Start by describing the brute force approach to show you understand the condition being checked. Then move to the prefix parity difference array, which reduces query time to O(1) after preprocessing. Interviewers typically expect this optimized O(n + q) solution because it demonstrates the ability to transform repeated range checks into prefix computations.
This approach involves iterating over each subarray defined by the queries and checking every adjacent pair for differing parity. The naive nature of this method makes it straightforward but potentially inefficient for larger inputs.
In this C solution, we iterate over each query range, checking adjacent pairs in the subarray for parity differences. If any pair has the same parity, the subarray is not special.
Time Complexity: O(queriesSize × numsSize).
Space Complexity: O(1) if output array is not considered.
This approach leverages the use of a prefix array to determine segment misfits based on parity changes. By preprocessing the array into a prefix difference array, each query can be answered in constant time by checking if any parity changes exist within the given range.
The C code creates a difference array storing whether adjacents differ in parity, then checks titles per query efficiently using this preprocessed information.
Time Complexity: O(n + q) where n = numsSize and q = queriesSize.
Space Complexity: O(n).
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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(queriesSize × numsSize). |
| Prefix Parity Difference Array | Time Complexity: O(n + q) where n = numsSize and q = queriesSize. |
| Record the Leftmost Special Array Position for Each Position | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray Check | O(q * n) | O(1) | Small arrays or few queries where simplicity matters more than performance |
| Prefix Parity Difference Array | O(n + q) | O(n) | Best general solution when many range queries must be answered quickly |
Special Array II | 3 Detailed Approaches | Beginners Alert | Leetcode 3152 | codestorywithMIK • codestorywithMIK • 8,878 views views
Watch 9 more video solutions →Practice Special Array II with our built-in code editor and test cases.
Practice on FleetCode