DDSA Solutions

3152. Special Array II

MediumView on LeetCode
ArrayBinary SearchPrefix Sum
Time: O(n + q)
Space: O(n)

Problem Overview

For each query [l,r]: check if subarray is special (adjacent parities alternate).

Intuition

For each query [l,r]: check if subarray is special (adjacent parities alternate). Prefix sum of "bad" pairs.

Algorithm

  1. 1Precompute bad[i] = 1 if nums[i]%2 == nums[i+1]%2. Prefix sum. Query [l,r] is special if sum of bad[l..r-1] == 0.

Common Pitfalls

  • •A subarray is special iff no bad adjacent pairs within it. Prefix sum for O(1) queries.
3152.cs
C#
// Approach: Prefix count of same-parity adjacent pairs; answer each query with range sum check.
// Time: O(n + q) Space: O(n)

public class Solution
{
    public bool[] IsArraySpecial(int[] nums, int[][] queries)
    {
        bool[] ans = new bool[queries.Length];
        // parityIds[i] := the id of the parity group that nums[i] belongs to
        int[] parityIds = new int[nums.Length];
        int id = 0;
        parityIds[0] = id;

        for (int i = 1; i < nums.Length; ++i)
        {
            if (nums[i] % 2 == nums[i - 1] % 2)
                ++id;
            parityIds[i] = id;
        }

        for (int i = 0; i < queries.Length; ++i)
        {
            int from = queries[i][0];
            int to = queries[i][1];
            ans[i] = parityIds[from] == parityIds[to];
        }

        return ans;
    }
}
Was this solution helpful?

Related Problems