We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Special Array II

Number: 3427

Difficulty: Medium

Paid? No

Companies: Microsoft, Amazon, Google, National Payments Corporation of India

Problem Description

Given an integer array nums and a series of queries, each query represented by a pair [from, to], determine if the subarray nums[from...to] is "special". An array is "special" if every adjacent pair in the subarray consists of one odd and one even integer. Return a boolean array where each element corresponds to whether the respective subarray is special.

Key Insights

  • The subarray is "special" if for every adjacent pair the numbers have different parities.
  • For a single element subarray, it is trivially special.
  • Precompute a helper array that marks for each adjacent pair in nums whether they have the same parity.
  • Build a prefix sum over this helper array to quickly count "invalid" pairs (pairs with same parity) in any queried range.
  • For each query [L, R], if there is any adjacent pair with the same parity (prefix sum difference > 0), the subarray is not special.

Space and Time Complexity

Time Complexity: O(n + q) where n is the number of elements in nums and q is the number of queries. Space Complexity: O(n) for the helper (prefix sum) array.

Solution

The solution uses a prefix sum technique to efficiently answer each query. First, iterate through the array to determine for each index i (from 0 to n-2) if nums[i] and nums[i+1] have the same parity. Store a value of 1 in a helper array for an invalid pair (same parity) and 0 otherwise. Then, compute the prefix sum of this helper array. For each query [L, R], check if there is any invalid adjacent pair between L and R-1 by subtracting the appropriate prefix sums. If the sum is 0, then the subarray is special; otherwise, it is not.

Code Solutions

# Python solution for Special Array II

def specialArrayII(nums, queries):
    n = len(nums)
    if n == 0:
        return []
    
    # Build an array where invalid[i] = 1 if nums[i] and nums[i+1] have the same parity, else 0
    invalid = [0] * (n - 1)
    for i in range(n - 1):
        if (nums[i] % 2) == (nums[i+1] % 2):
            invalid[i] = 1

    # Build prefix sum array for invalid array
    prefix = [0] * (n - 1)
    prefix[0] = invalid[0]
    for i in range(1, n - 1):
        prefix[i] = prefix[i - 1] + invalid[i]

    result = []
    for L, R in queries:
        # a subarray with a single element is always special
        if L == R:
            result.append(True)
        else:
            # Calculate the number of invalid pairs in the range [L, R-1]
            invalidCount = prefix[R - 1] - (prefix[L - 1] if L > 0 else 0)
            result.append(invalidCount == 0)
    return result

# Example usage:
nums = [3,4,1,2,6]
queries = [[0,4]]
print(specialArrayII(nums, queries))  # Expected output: [False]
← Back to All Questions