Alternating Groups II
Asked at Capital One
Problem
Alternating Groups II gives you a circle of red and blue tiles and asks how many groups of k consecutive tiles alternate in color. Because the tiles form a circle, windows can wrap around the end. Tracking the current run of alternating tiles while walking n + k - 1 positions handles it in linear time.
Asked At
| Company | Difficulty | |
|---|---|---|
| Capital One | Medium | View all Capital One questions → |
How to Think About It
Checking every window of size k directly is O(n * k).
Key insight: a window of size k ending at position i alternates iff the current alternating run ending at i has length at least k.
Maintain run: if colors[i] != colors[i-1], extend the run; otherwise reset it to 1.
For circularity, walk indices i = 1 .. n + k - 2 and read colors[i % n]. Count a window whenever i >= k - 1 and run >= k. That checks exactly n windows, one per starting tile.
Walkthrough: [0,1,0,1,0], k = 3: the run keeps growing across the linear part, but the wrap from index 4 (0) to index 0 (0) resets it. 3 windows qualify.
Optimal Approach
Step 1: run = 1, count = 0.
Step 2: For i from 1 to n + k - 2:
If colors[i % n] != colors[(i - 1) % n]: run += 1, else run = 1.
If i >= k - 1 and run >= k: count += 1.
Step 3: Return count.
Time: O(n + k). Space: O(1).
What Trips People Up in Real Interviews
Forgetting the circular windows that wrap from the end back to the start.
Walking too far around the circle and counting some windows twice — the loop must check exactly n windows.
Copying the array to double it — fine, but indexing modulo n avoids the extra memory.
Resetting the run to 0 instead of 1 on a repeated color.
Solution Code
def numberOfAlternatingGroups(colors, k):
n = len(colors)
run = 1
count = 0
for i in range(1, n + k - 1):
if colors[i % n] != colors[(i - 1) % n]:
run += 1
else:
run = 1
if i >= k - 1 and run >= k:
count += 1
return countFrequently Asked Questions
What is the Alternating Groups II problem?
Alternating Groups II gives you a circle of red and blue tiles and asks how many groups of `k` consecutive tiles alternate in color. Because the tiles form a circle, windows can wrap around the end. Tracking the current run of alternating tiles while walking `n + k - 1` positions handles it in linear time.
How do you solve Alternating Groups II?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Alternating Groups II?
Alternating Groups II is asked at Capital One. It is a medium difficulty problem.
What are common mistakes on Alternating Groups II?
- Forgetting the circular windows that wrap from the end back to the start.
- Walking too far around the circle and counting some windows twice — the loop must check exactly `n` windows.
- Copying the array to double it — fine, but indexing modulo `n` avoids the extra memory.
- Resetting the run to 0 instead of 1 on a repeated color.