DDSA Solutions

3208. Alternating Groups II

UnknownView on LeetCode
ArraySliding Window
Time: O(n)
Space: O(1)

Problem Overview

Count subarrays where AND of all elements equals target.

Intuition

Count subarrays where AND of all elements equals target. Sliding window on AND (only decreases).

Algorithm

  1. 1For each right: maintain set of distinct AND values ending at right (at most 30 values since AND decreases).
  2. 2Count values equal to target.

Common Pitfalls

  • •Set of AND values shrinks as we move left. At most log(max) distinct values per right endpoint.
3208.cs
C#
// Approach: Sliding window of size k on circular array with duplicate prefix; count valid alternating windows.
// Time: O(n) Space: O(1)

public class Solution
{
    public int NumberOfAlternatingGroups(int[] colors, int k)
    {
        int n = colors.Length;
        int ans = 0, cnt = 0;
        for (int i = 0; i < n << 1; ++i)
        {
            if (i > 0 && colors[i % n] == colors[(i - 1) % n])
                cnt = 1;
            else
                ++cnt;
                
            ans += i >= n && cnt >= k ? 1 : 0;
        }
        return ans;
    }
}
Was this solution helpful?

Related Problems