Alternating Groups II — Medium Problem & Solution

Problem statement

There is a circle of tiles, colors[i] being 0 for a red tile and 1 for a blue one. The last tile and the first are neighbours.

An alternating group is a run of k consecutive tiles (going around the circle) in which every tile differs in colour from the one before it. Return how many alternating groups there are — one per starting position.

Example 1

Input: colors = [0,1,0,1,0], k = 3
Output: 3
Explanation: The groups starting at indices 0, 1 and 2.

Example 2

Input: colors = [0,1,0,0,1,0,1], k = 6
Output: 2

Example 3

Input: colors = [1,1,0,1], k = 4
Output: 0
Explanation: The two leading blues break every window.

Constraints

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

How to solve Alternating Groups II

Keep a running "alternating streak ending here" length while walking the circle. Whenever the streak is at least k, the window ending at this tile is an alternating group. Walking n + k - 2 steps with modular indexing covers every wrap-around window exactly once.

Approach

1. Start run = 1 at index 0.
2. For i from 1 to n + k - 2: if colors[i mod n] differs from colors[(i-1) mod n], extend the run; otherwise reset it to 1.
3. Count a group whenever run >= k.

Why it works

Counting windows by their end is what makes one pass enough — a streak of length L >= k contributes exactly L - k + 1 windows, and incrementing at every step where run >= k adds up to precisely that. The extra k - 1 steps are the minimum needed to see every window that straddles the seam, and no more, so nothing is double-counted.

Complexity

• Time — O(n + k)
• Space — O(1)

Pitfalls

• Stopping at index n - 1 misses every group that crosses the seam.
• Walking a full 2n steps would count the wrap-around windows twice when k is small.
• Reset the run to 1, not 0 — the current tile always starts a fresh streak.

Reference solution

Python

from typing import List

def numberOfAlternatingGroups(colors: List[int], k: int) -> int:
    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 run >= k:
            count += 1
    return count

JavaScript

var numberOfAlternatingGroups = function(colors, k) {
    var n = colors.length, run = 1, count = 0;
    for (var i = 1; i < n + k - 1; i++) {
        if (colors[i % n] !== colors[(i - 1) % n]) run++; else run = 1;
        if (run >= k) count++;
    }
    return count;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Minimum Number of Increments on Subarrays to Form a Target Array Medium
• Find the Winner of an Array Game Medium
• Queries on a Permutation With Key Medium
• Corporate Flight Bookings Medium
• Find the Winner of the Circular Game Medium
• Longest Subsequence With Limited Sum Medium