MediumArraySliding WindowUpdated Sep 2026

3208. Alternating Groups II

Asked at Capital One

Difficulty

Medium

Time

O(n + k)

Space

O(1)

Pattern

Array

Companies

1

Problem

You are given an array colors that describes a circle of tiles. Each value is 0 (red) or 1 (blue). You are also given an integer k.

A group is any k tiles that sit next to each other in the circle. The group is alternating when the colors keep flipping: every tile in the group has a different color from the tile right before it. In other words, no two neighbours inside the group share the same color.

Return how many alternating groups exist. Because the tiles form a circle, the last tile and the first tile are neighbours, so a group may wrap around the end of the array. Every starting tile gives exactly one group, so there are n groups in total to consider.

A circle of tiles, windows of size k

k = 30101001234Window starting at index 0: 0,1,0 — it alternates, soit countswraps to index 00101001234Window starting at index 3: 1,0 then wrap to 0 — thetwo 0s break it
Windows may wrap past the last tile, so the pair (last, first) also has to alternate.

Constraints

  • ●3 <= colors.length <= 10^5
  • ●0 <= colors[i] <= 1
  • ●3 <= k <= colors.length

Examples

Example 1
Inputcolors = [0,1,0,1,0], k = 3
Output3
WhyThe circle is 0,1,0,1,0 and then back to 0. The three groups starting at index 0, 1 and 2 are 0-1-0, 1-0-1 and 0-1-0, and all of them alternate. The group starting at index 3 is 1-0-0 (it wraps to the first tile) and the one at index 4 is 0-0-1; both have a repeated colour, so they fail. That leaves
Example 2
Inputcolors = [0,1,0,0,1,0,1], k = 6
Output2
WhyOnly two length-6 stretches alternate: the one starting at index 1 (1,0,0,...) is broken by the two 0s, so the good ones are the windows starting at index 4 and index 5, which wrap around and still flip colour at every step. Hence 2.
Example 3
Inputcolors = [1,1,0,1], k = 4
Output0
WhyThe first two tiles are both 1, so every length-4 window contains that repeated pair. No window alternates, so the answer is 0.

Asked At

1 companies
CompanyDifficulty
Capital OneMediumView all Capital One questions →

How to Think About It

1

Checking every window of size k directly is O(n * k).

2

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.

3

Maintain run: if colors[i] != colors[i-1], extend the run; otherwise reset it to 1.

4

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.

5

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).

Track the current alternating run

0101001234ii = 2: colours differ from the previous tile, so rungrows to 3 and the first window counts0101001234ii = 4: still alternating, run = 5, so windows endinghere also count0101001234i % ni = 5 wraps to index 0: colour 0 equals the previouscolour 0, so run resets to 1if colors[i%n] != colors[(i-1)%n]: run += 1else: run = 1count += 1 when i >= k-1 and run >= k
A window of size k is good exactly when the alternating run ending at its last tile is at least k.
ComplexityTime O(n + k)Space O(1)We walk n + k - 1 positions once and keep only a running length, so the cost is linear in the input size plus k.

What Trips People Up in Real Interviews

1

Forgetting the circular windows that wrap from the end back to the start.

2

Walking too far around the circle and counting some windows twice — the loop must check exactly n windows.

3

Copying the array to double it — fine, but indexing modulo n avoids the extra memory.

4

Resetting the run to 0 instead of 1 on a repeated color.

Solution Code

O(n + k) time
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 count

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 runs in O(n + k) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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.