LeetCode 3152 - Special Array II

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Prefix Sum

Solution

Problem Understanding

We are given an integer array nums and several queries. Each query specifies a subarray using two indices [fromi, toi]. For every query, we must determine whether the subarray nums[fromi..toi] is a special array.

A subarray is considered special if every adjacent pair of elements has different parity. In other words:

An even number must always be followed by an odd number
An odd number must always be followed by an even number

Two neighboring even numbers are invalid, and two neighboring odd numbers are also invalid.

For example:

[3, 4, 1, 2] is special because the parity alternates at every step
[3, 4, 1, 2, 6] is not special because 2 and 6 are both even

The input consists of:

nums, the original array
queries, where each query asks whether a particular subarray is special

The output must be a boolean array where each element corresponds to one query result.

The constraints are important:

nums.length can be up to 10^5
queries.length can also be up to 10^5

This immediately tells us that a naive solution that scans every subarray for every query will likely be too slow. In the worst case, checking every query independently would require up to 10^10 operations.

Several edge cases are important:

A subarray containing only one element is always special because there are no adjacent pairs to violate the condition.
Arrays with all even or all odd values create many invalid adjacent pairs.
Queries may overlap heavily, so repeated work should be avoided.
Very large inputs require an efficient preprocessing strategy.

Approaches

Brute Force Approach

The straightforward solution is to process every query independently.

For each query [left, right], we scan the subarray from left to right - 1 and check every adjacent pair:

If two adjacent numbers have the same parity, the subarray is not special.
Otherwise, continue checking until the end.

This approach is correct because it directly implements the problem definition. However, it is inefficient for large inputs.

If there are q queries and each query scans up to n elements, the worst-case complexity becomes O(n * q), which is too slow for 10^5 sized inputs.

Optimal Prefix Sum Approach

The key observation is that a subarray is special if and only if there are no adjacent pairs with the same parity inside that range.

Instead of checking each query separately, we preprocess the array and mark every "bad" position:

A position i is bad if nums[i] and nums[i - 1] have the same parity.

Then we build a prefix sum array that stores how many bad positions appear up to each index.

For a query [left, right], we only need to know whether any bad position exists inside that range.

If the count of bad positions is zero, the subarray is special.

This transforms repeated scanning into constant-time query checks after linear preprocessing.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × q)	O(1)	Checks every adjacent pair for every query
Optimal	O(n + q)	O(n)	Uses prefix sums to detect invalid parity pairs quickly

Algorithm Walkthrough

Create an array called badPairs.

For every index i from 1 to n - 1, check whether nums[i] and nums[i - 1] have the same parity.

If they do, mark that position as bad.

A pair has the same parity when:

$nums[i] \bmod 2 = nums[i-1] \bmod 2$ 2. Build a prefix sum array.

Let prefix[i] represent the number of bad adjacent pairs among indices 0 through i.

This allows us to quickly compute how many bad pairs exist inside any query range. 3. Process each query [left, right].

Any bad adjacent pair inside the subarray must occur between indices:

left and left + 1
left + 1 and left + 2
...
right - 1 and right

Therefore, we need to count bad positions from left + 1 through right. 4. Use the prefix sums to compute the number of bad pairs in constant time.

The count is:

prefix[right] - prefix[left]

If this value is zero, the subarray is special.

Otherwise, it is not special. 5. Store the boolean result for each query and return the final list.

Why it works

The algorithm works because every violation of the special-array condition corresponds exactly to one adjacent pair having the same parity.

The prefix sum array stores the cumulative number of such violations. For any query range, if the number of violations inside the range is zero, then every adjacent pair alternates parity correctly, so the subarray is special. If even one violation exists, the subarray cannot be special.

Python Solution

from typing import List

class Solution:
    def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:
        n = len(nums)

        # prefix[i] = number of bad adjacent pairs up to index i
        prefix = [0] * n

        for i in range(1, n):
            prefix[i] = prefix[i - 1]

            if nums[i] % 2 == nums[i - 1] % 2:
                prefix[i] += 1

        result = []

        for left, right in queries:
            bad_count = prefix[right] - prefix[left]
            result.append(bad_count == 0)

        return result

The implementation begins by creating a prefix sum array named prefix.

Each position stores the total number of bad adjacent pairs encountered so far. A bad pair occurs when two neighboring numbers have the same parity.

During preprocessing:

if nums[i] % 2 == nums[i - 1] % 2:

we detect invalid adjacent pairs and increment the prefix count.

After preprocessing, every query can be answered in constant time.

The expression:

prefix[right] - prefix[left]

computes how many bad adjacent pairs exist inside the subarray.

If the count is zero, the subarray satisfies the alternating parity requirement.

Go Solution

func isArraySpecial(nums []int, queries [][]int) []bool {
	n := len(nums)

	// prefix[i] = number of bad adjacent pairs up to index i
	prefix := make([]int, n)

	for i := 1; i < n; i++ {
		prefix[i] = prefix[i-1]

		if nums[i]%2 == nums[i-1]%2 {
			prefix[i]++
		}
	}

	result := make([]bool, 0, len(queries))

	for _, query := range queries {
		left := query[0]
		right := query[1]

		badCount := prefix[right] - prefix[left]
		result = append(result, badCount == 0)
	}

	return result
}

The Go implementation follows the same logic as the Python solution.

Slices are used instead of Python lists. The prefix sum array is created with make([]int, n), and results are stored in a boolean slice.

There are no integer overflow concerns because the maximum prefix value is at most n, which fits comfortably inside Go's int type.

Worked Examples

Example 1

Input:

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

Step 1: Build Prefix Array

i	nums[i-1]	nums[i]	Same Parity?	prefix[i]
0	-	3	-	0
1	3	4	No	0
2	4	1	No	0
3	1	2	No	0
4	2	6	Yes	1

Final prefix array:

[0,0,0,0,1]

Step 2: Process Query

Query: [0,4]

Compute:

prefix[4] - prefix[0] = 1 - 0 = 1

Since the result is not zero, the subarray is not special.

Output:

[false]

Example 2

Input:

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

Step 1: Build Prefix Array

i	nums[i-1]	nums[i]	Same Parity?	prefix[i]
0	-	4	-	0
1	4	3	No	0
2	3	1	Yes	1
3	1	6	No	1

Final prefix array:

[0,0,1,1]

Step 2: Process Queries

Query `[0,2]`

prefix[2] - prefix[0] = 1 - 0 = 1

Not special.

Query `[2,3]`

prefix[3] - prefix[2] = 1 - 1 = 0

Special.

Output:

[false,true]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + q)	One pass to build prefix sums and one pass through queries
Space	O(n)	Prefix sum array stores one value per index

The preprocessing step scans the array once, requiring O(n) time. Each query is answered in constant time using prefix sums, so processing all queries takes O(q) time.

The prefix array requires O(n) additional memory.

Test Cases

from typing import List

class Solution:
    def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:
        n = len(nums)

        prefix = [0] * n

        for i in range(1, n):
            prefix[i] = prefix[i - 1]

            if nums[i] % 2 == nums[i - 1] % 2:
                prefix[i] += 1

        result = []

        for left, right in queries:
            result.append(prefix[right] - prefix[left] == 0)

        return result

sol = Solution()

# Provided example 1
assert sol.isArraySpecial([3,4,1,2,6], [[0,4]]) == [False]

# Provided example 2
assert sol.isArraySpecial([4,3,1,6], [[0,2],[2,3]]) == [False, True]

# Single element subarray
assert sol.isArraySpecial([7], [[0,0]]) == [True]

# Fully alternating parity
assert sol.isArraySpecial([1,2,3,4,5], [[0,4],[1,3]]) == [True, True]

# All even numbers
assert sol.isArraySpecial([2,4,6,8], [[0,3],[1,2]]) == [False, False]

# All odd numbers
assert sol.isArraySpecial([1,3,5,7], [[0,3]]) == [False]

# Query covering valid small range
assert sol.isArraySpecial([2,1,4,3], [[1,2]]) == [True]

# Query containing one bad pair
assert sol.isArraySpecial([2,1,3,4], [[0,2]]) == [False]

# Multiple overlapping queries
assert sol.isArraySpecial(
    [1,2,4,5,7,8],
    [[0,1],[0,2],[1,4],[3,5]]
) == [True, False, False, True]

# Minimum size array
assert sol.isArraySpecial([2], [[0,0]]) == [True]

# Large alternating pattern
nums = [i % 2 for i in range(1000)]
assert sol.isArraySpecial(nums, [[0,999]]) == [True]

Test	Why
`[3,4,1,2,6]`	Validates detection of an even-even adjacent pair
`[4,3,1,6]`	Tests mixed query results
Single element array	Ensures length-1 subarrays are always special
Fully alternating array	Confirms valid arrays return true
All even numbers	Tests repeated parity violations
All odd numbers	Tests another repeated violation pattern
Small valid range	Verifies partial subarray correctness
One bad pair	Ensures detection inside query range
Overlapping queries	Confirms prefix sums work across many ranges
Minimum constraints	Tests smallest possible input
Large alternating pattern	Stress-tests performance and correctness

Edge Cases

A single-element subarray is an important edge case because there are no adjacent pairs to compare. Some implementations accidentally treat this as invalid or attempt out-of-bounds comparisons. This solution handles it naturally because the prefix difference becomes zero, so the query correctly returns True.

Arrays where every number has the same parity can also expose bugs. For example, [2,4,6,8] contains a bad pair at every adjacent position. Incorrect implementations may miss overlapping violations or stop checking too early. The prefix sum approach records every invalid transition independently, so all problematic ranges are detected correctly.

Queries that start and end at adjacent indices are another subtle case. For example, querying [2,3] only checks one pair. Off-by-one mistakes are common here because the adjacent-pair indices differ from the element indices. The formula:

prefix[right] - prefix[left]

correctly counts only the bad pairs fully contained inside the query range.

Large inputs with 10^5 elements and 10^5 queries are also critical. A brute-force solution would time out because it repeatedly scans subarrays. This implementation preprocesses the array once and answers each query in constant time, making it efficient enough for the maximum constraints.

LeetCode 3152 - Special Array II

Solution

Problem Understanding

Approaches

Brute Force Approach

Optimal Prefix Sum Approach

Algorithm Walkthrough

Why it works

Python Solution

Go Solution

Worked Examples

Example 1

Step 1: Build Prefix Array

Step 2: Process Query

Example 2

Step 1: Build Prefix Array

Step 2: Process Queries

Query [0,2]

Query [2,3]

Complexity Analysis

Test Cases

Edge Cases

Query `[0,2]`

Query `[2,3]`