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
- Build a difference array
diff[i] = 1whencolors[i] != colors[(i+1) % n], i.e. when the edge between consecutive tiles alternates. - An alternating group of size
kstarting atirequires thek - 1consecutive edges fromito all be alternating. - Duplicate
diffto handle the circularity, then use a prefix sum to test each of thenstarting positions in O(1). - The answer is the number of starting positions whose
k - 1edges 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
kedges instead ofk - 1: a group ofktiles has exactlyk - 1internal edges. - Not handling
k == 1: every single tile is an alternating group, so the answer isn. - Counting groups of length greater than
k: the window is exactlymedges, 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.
🧩 Related Sliding Window Problems
#219 · #219Contains Duplicate II#220 · #121Best Time to Buy and Sell Stock#221 · #2379Minimum Recolors to Get K Consecutive Black Blocks#222 · #1984Minimum Difference Between Highest and Lowest of K Scores#223 · #1343Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold#224 · #1052Grumpy Bookstore Owner