LeetCode 3152: Special Array II

Problem Description

LeetCode Problem 3152

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:

Example 2:

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

Difficulty: Medium

Tags: array, binary search, prefix sum

Rating: 93.58%

Solution Approach

Naive Solution $O(N*Q)$

The straightforward approach processes each query independently:

def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:
    def isSpecial(nums, i, j):
        parity = nums[i] % 2
        for idx in range(i+1, j+1):
            p = nums[idx] % 2
            if p == parity:
                return False
            parity = p
        return True
    
    res = []
    for q in queries:
        res.append(isSpecial(nums, q[0], q[1]))
    return res

This solution:

1. For each query, we check all elements in the range
2. We keep track of the previous element’s parity
3. If we find two adjacent elements with the same parity, we return False
4. If we complete the check without finding same-parity pairs, we return True

However, this approach is inefficient for large numbers of queries, as we repeatedly check the same pairs.

Optimized Solution $O(N+Q)$

We can improve performance by preprocessing the array to identify problematic pairs:

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

    # Store positions where adjacent elements have same parity
    same_parity = [0] * (n-1)
    for i in range(n-1):
        if nums[i] % 2 == nums[i+1] % 2:
            same_parity[i] = 1
            
    # Prefix sum array for quick range queries
    prefix = [0] * n
    if n > 1:
        prefix[1] = same_parity[0]
        for i in range(2, n):
            prefix[i] = prefix[i-1] + same_parity[i-1]
    
    # Process queries
    res = []
    for i, j in queries:
        if i == j:
            res.append(True)
            continue
        
        count = prefix[j] - (prefix[i] if i > 0 else 0)
        res.append(count == 0)
    return res

This optimized solution uses three key techniques:

1. Precomputing Same-Parity Pairs:

   • We create an array same_parity where each position indicates if adjacent elements have the same parity
   • A value of 1 means we found a problem (same parity), 0 means the pair is valid

2. Prefix Sum Array:

   • We build a prefix sum array to enable quick range queries
   • Each position stores the count of same-parity pairs up to that point
   • This allows us to find the number of same-parity pairs in any range with simple subtraction

3. Efficient Query Processing:

   • For each query [i,j], we can find the number of same-parity pairs in O(1) time
   • If there are no same-parity pairs in the range (count = 0), the subarray is special
   • Single-element queries are always special

Complexity Analysis

Naive Solution:

• Time Complexity: $O(N*Q)$ where N is array length and Q is number of queries
• Space Complexity: $O(1)$ - only storing the result array

Optimized Solution:

• Time Complexity: $O(N + Q)$
  • O(N) for preprocessing (creating same_parity and prefix arrays)
  • O(Q) for processing all queries
• Space Complexity: $O(N)$ for storing the auxiliary arrays