⚡Flashcard Drill➔
NeetCode #229LC-3208MediumSliding Window
← Back to All Problems

#229 · #3208 · Alternating Groups II(交替组 II)

📌 Problem Statement & Constraints

There is a circle of colors[i] (0 or 1) and an integer k. An alternating group of size k is k consecutive tiles on the circle whose colours alternate. Return the number of such groups. Constraints: 3 <= colors.length <= 10^5, colors[i] is 0 or 1, 1 <= k <= colors.length.

💡 Core Algorithmic Approaches

  1. Build a difference array diff[i] = 1 when colors[i] != colors[(i+1) % n], i.e. when the edge between consecutive tiles alternates.
  2. An alternating group of size k starting at i requires the k - 1 consecutive edges from i to all be alternating.
  3. Duplicate diff to handle the circularity, then use a prefix sum to test each of the n starting positions in O(1).
  4. The answer is the number of starting positions whose k - 1 edges are all 1.

💻 Benchmark Python3 Implementation

class Solution:
    def numberOfAlternatingGroups(self, colors: List[int], k: int) -> int:
        n = len(colors)
        m = k - 1                      # number of edges a group requires
        if m == 0:
            return n                   # k == 1: every tile is a group
        diff = [1 if colors[i] != colors[(i + 1) % n] else 0 for i in range(n)]
        dd = diff + diff               # doubled to handle wrap-around
        pref = [0] * (2 * n + 1)
        for i in range(2 * n):
            pref[i + 1] = pref[i] + dd[i]
        res = 0
        for start in range(n):
            # the m edges starting at `start` must all alternate
            if pref[start + m] - pref[start] == m:
                res += 1
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): building the difference array, the prefix sums and the final scan are all linear.
💾 Space Complexity
O(n) for the doubled difference and prefix arrays.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the circular wrap-around: a group may cross the index boundary, which the doubled array handles.
  • Using k edges instead of k - 1: a group of k tiles has exactly k - 1 internal edges.
  • Not handling k == 1: every single tile is an alternating group, so the answer is n.
  • Counting groups of length greater than k: the window is exactly m edges, so the prefix check is exact.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Sliding Window Problems