Watch 10 video solutions for Special Array II, a medium level problem involving Array, Binary Search, Prefix Sum. This walkthrough by codestorywithMIK has 8,878 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |