3208. Alternating Groups II

UnknownView on LeetCode

Array Sliding Window

Time: O(n)

Space: O(1)

Intuition

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

Algorithm

1For each right: maintain set of distinct AND values ending at right (at most 30 values since AND decreases).
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

// 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?