Skip to main content
Talentd

Special Array II - Solution & Explanation

MediumArrayBinary SearchPrefix Sum14 min readAsked at: Amazon, Microsoft, Bloomberg +1
Practice this problem

Problem Statement

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:

  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

Approach Overview

Problem 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 1: Brute Force Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(queriesSize × numsSize).
Space Complexity: O(1) if output array is not considered.

Try this approach in the editor →

Approach 2: Prefix Parity Difference Array

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + q) where n = numsSize and q = queriesSize.
Space Complexity: O(n).

Try this approach in the editor →

Approach 3: Record the Leftmost Special Array Position for Each Position

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach

Time Complexity: O(queriesSize × numsSize).
Space Complexity: O(1) if output array is not considered.

Prefix Parity Difference Array

Time Complexity: O(n + q) where n = numsSize and q = queriesSize.
Space Complexity: O(n).

Record the Leftmost Special Array Position for Each Position—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subarray CheckO(q * n)O(1)Small arrays or few queries where simplicity matters more than performance
Prefix Parity Difference ArrayO(n + q)O(n)Best general solution when many range queries must be answered quickly

Video Solution

Special Array II | 3 Detailed Approaches | Beginners Alert | Leetcode 3152 | codestorywithMIK • codestorywithMIK • 8,989 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Special Array II easy or hard?
Special Array II is rated Medium because the brute force solution is straightforward but inefficient. Recognizing that adjacent parity checks can be preprocessed with prefix sums is the key step that makes the problem efficient.
Special Array II Python/Java solution
Most implementations first compute a prefix array of parity violations, then answer each query using prefix differences. The logic is identical across Python, Java, C++, and other languages, with overall complexity O(n + q) time and O(n) space.
How to solve Special Array II in O(n)?
Precompute an array marking parity violations: bad[i] = 1 if nums[i] and nums[i-1] have the same parity. Build a prefix sum over this array. For a query [l, r], check whether the prefix sum difference between r and l+1 is zero. If it is zero, the subarray is special.
What is the best approach for Special Array II?
The most efficient solution uses a prefix parity difference array. Precompute positions where adjacent elements share the same parity, store them in a prefix sum, and answer each query by checking if any violations exist in the range. This reduces query time to O(1) after O(n) preprocessing.
Is Special Array II asked at Google/Amazon/Meta?
Problems involving prefix sums, parity checks, and range queries frequently appear in interviews at companies like Google, Amazon, and Meta. Special Array II reflects a common pattern where preprocessing allows fast query evaluation.
What data structure is used in Special Array II?
The main structure is a prefix sum array built from a parity violation indicator array. This allows constant-time range checks to determine whether any adjacent elements in a subarray share the same parity.
What is the time complexity of Special Array II?
The optimal prefix sum approach runs in O(n + q) time, where n is the array length and q is the number of queries. Preprocessing the parity violations takes O(n), and each query is answered in constant time using prefix sums.

Ready to solve this problem?

Practice Special Array II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays