Difficulty: 🟡 Medium
Topics: Array, Sliding Window

Solution

LeetCode 3208 - Alternating Groups II

Problem Understanding

The problem gives us a circular array called colors, where each value represents a tile color. A value of 0 means red, and a value of 1 means blue. We are also given an integer k.

We must count how many groups of exactly k contiguous tiles form an alternating sequence. Since the tiles are arranged in a circle, the array wraps around, meaning the tile after the last index is the first tile again.

An alternating group means that every adjacent pair inside the group must have different colors. For example:

[0,1,0,1] is alternating
[1,0,1] is alternating
[0,0,1] is not alternating because two neighboring tiles are equal

The key detail is that we are working with a circular structure. A valid group may begin near the end of the array and continue at the beginning.

The input size can be as large as 10^5, which immediately tells us that an O(n * k) brute force solution may become too slow in the worst case. We need a more efficient linear time approach.

Several edge cases are important:

The entire circle may already alternate perfectly.
There may be no alternating segments at all.
The valid segment may wrap around the end of the array.
k can equal the entire array length, meaning we must verify whether the whole circle alternates.
Consecutive equal values can break multiple candidate windows at once.

Understanding how to efficiently track alternating behavior across a circular array is the core challenge of the problem.

Approaches

Brute Force Approach

The most direct solution is to examine every possible starting position in the circle.

For each starting index, we check the next k elements one by one and verify whether every adjacent pair alternates. Since the array is circular, we use modulo arithmetic to wrap indices back to the beginning.

If all adjacent pairs differ, then that window is a valid alternating group.

This approach is correct because it explicitly validates every possible group independently. However, it is inefficient because each of the n starting positions may require checking up to k - 1 adjacent pairs.

With n up to 10^5, this worst case complexity becomes too large.

Optimal Sliding Window Observation

The important observation is that we do not need to repeatedly recheck the same adjacent relationships.

A window of size k is alternating if all k - 1 adjacent pairs inside that window are different.

Instead of validating every window from scratch, we can process the array in one pass while maintaining the length of the current alternating streak.

Because the array is circular, we simulate wraparound by iterating through n + k - 1 elements using modulo indexing.

At every step:

If the current tile differs from the previous tile, the alternating streak increases.
Otherwise, the streak resets to 1.

Whenever the alternating streak becomes at least k, we know a valid alternating group ends at the current position.

This converts repeated work into a single linear scan.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(nk)	O(1)	Checks every window independently
Optimal	O(n)	O(1)	Uses sliding alternating streak

Algorithm Walkthrough

Let n be the length of the array.
Initialize a variable called alternating_length to 1. This represents the current length of the consecutive alternating sequence ending at the current position.
Initialize result to 0. This will store the number of valid alternating groups.
Iterate through indices from 1 to n + k - 2.

We extend beyond n so that windows wrapping around the circular boundary are also examined. 5. For each index i, compare:

colors[i % n]
colors[(i - 1) % n]

The modulo operation simulates the circular structure. 6. If the two colors are different:

Increment alternating_length by 1

Otherwise:

Reset alternating_length to 1

Whenever alternating_length >= k, we found a valid alternating window ending at the current position.

Increment result. 8. Return result.

Why it works

The algorithm maintains the invariant that alternating_length always equals the length of the longest alternating suffix ending at the current index.

A window of size k is alternating exactly when the last k elements form a valid alternating sequence. Therefore, whenever alternating_length >= k, there exists a valid alternating group ending at the current position.

Because the scan includes wraparound positions using modulo arithmetic, every circular window is considered exactly once.

Python Solution

from typing import List

class Solution:
    def numberOfAlternatingGroups(self, colors: List[int], k: int) -> int:
        n = len(colors)
        
        alternating_length = 1
        result = 0
        
        for i in range(1, n + k - 1):
            current = colors[i % n]
            previous = colors[(i - 1) % n]
            
            if current != previous:
                alternating_length += 1
            else:
                alternating_length = 1
            
            if alternating_length >= k:
                result += 1
        
        return result

The implementation begins by storing the array length in n.

The variable alternating_length tracks the size of the current alternating streak. Initially, a single element always forms a valid alternating sequence of length 1.

The loop runs from 1 through n + k - 2. This range is carefully chosen so that every circular window of size k is examined exactly once.

Inside the loop, modulo indexing is used to simulate circular traversal. If the current color differs from the previous color, the alternating streak extends. Otherwise, the streak resets because alternation has been broken.

Whenever the streak length becomes at least k, we know a valid alternating group exists ending at the current position, so we increment the answer.

Finally, the total count is returned.

Go Solution

func numberOfAlternatingGroups(colors []int, k int) int {
    n := len(colors)

    alternatingLength := 1
    result := 0

    for i := 1; i < n+k-1; i++ {
        current := colors[i%n]
        previous := colors[(i-1)%n]

        if current != previous {
            alternatingLength++
        } else {
            alternatingLength = 1
        }

        if alternatingLength >= k {
            result++
        }
    }

    return result
}

The Go implementation follows the same logic as the Python version.

Go uses integer arithmetic directly for modulo operations, and slices naturally represent the array. No additional memory structures are required.

Since the constraints are relatively small for integer multiplication and counting, standard Go int values are sufficient without overflow concerns.

Worked Examples

Example 1

Input:

colors = [0,1,0,1,0]
k = 3

We iterate through n + k - 1 = 7 positions.

i	Current	Previous	Alternating Length	Result
1	1	0	2	0
2	0	1	3	1
3	1	0	4	2
4	0	1	5	3
5	0	0	1	3
6	1	0	2	3

Final answer:

Example 2

Input:

colors = [0,1,0,0,1,0,1]
k = 6

i	Current	Previous	Alternating Length	Result
1	1	0	2	0
2	0	1	3	0
3	0	0	1	0
4	1	0	2	0
5	0	1	3	0
6	1	0	4	0
7	0	1	5	0
8	1	0	6	1
9	0	1	7	2
10	0	0	1	2
11	1	0	2	2

Final answer:

Example 3

Input:

colors = [1,1,0,1]
k = 4

i	Current	Previous	Alternating Length
1	1	1	1
2	0	1	2
3	1	0	3
4	1	1	1
5	1	1	1
6	0	1	2

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each position is processed once
Space	O(1)	Only a few variables are used

The algorithm performs a single pass over approximately n + k positions. Since k <= n, this simplifies to linear complexity.

No auxiliary arrays, stacks, or hash maps are needed, so the extra memory usage remains constant.

Test Cases

from typing import List

class Solution:
    def numberOfAlternatingGroups(self, colors: List[int], k: int) -> int:
        n = len(colors)

        alternating_length = 1
        result = 0

        for i in range(1, n + k - 1):
            current = colors[i % n]
            previous = colors[(i - 1) % n]

            if current != previous:
                alternating_length += 1
            else:
                alternating_length = 1

            if alternating_length >= k:
                result += 1

        return result

solution = Solution()

assert solution.numberOfAlternatingGroups([0,1,0,1,0], 3) == 3  # Example 1
assert solution.numberOfAlternatingGroups([0,1,0,0,1,0,1], 6) == 2  # Example 2
assert solution.numberOfAlternatingGroups([1,1,0,1], 4) == 0  # Example 3

assert solution.numberOfAlternatingGroups([0,1,0], 3) == 1  # Smallest valid alternating circle
assert solution.numberOfAlternatingGroups([0,0,0], 3) == 0  # No alternation anywhere
assert solution.numberOfAlternatingGroups([0,1,0,1], 4) == 4  # Entire circle alternates
assert solution.numberOfAlternatingGroups([1,0,1,0,1], 5) == 1  # Full-length alternating window
assert solution.numberOfAlternatingGroups([0,1,1,0,1], 3) == 3  # Mixed alternating segments
assert solution.numberOfAlternatingGroups([0,1,0,1,0,1], 2) == 6  # Every adjacent pair alternates
assert solution.numberOfAlternatingGroups([1,1,1,1,1], 3) == 0  # Completely uniform array

Test	Why
`[0,1,0,1,0], k=3`	Verifies standard alternating behavior
`[0,1,0,0,1,0,1], k=6`	Verifies long circular windows
`[1,1,0,1], k=4`	Verifies no valid groups
`[0,1,0], k=3`	Smallest valid input
`[0,0,0], k=3`	Confirms identical values fail
`[0,1,0,1], k=4`	Entire circle alternates
`[1,0,1,0,1], k=5`	Tests full-length window
`[0,1,1,0,1], k=3`	Tests reset behavior
`[0,1,0,1,0,1], k=2`	Every adjacent pair valid
`[1,1,1,1,1], k=3`	Uniform array edge case

Edge Cases

Entire Array Alternates

Consider:

colors = [0,1,0,1]
k = 4

The whole circle alternates perfectly. A common bug is failing to account for wraparound windows correctly. The modulo indexing ensures that circular adjacency is handled naturally, allowing all valid starting positions to be counted.

Consecutive Equal Values

Consider:

colors = [0,0,1,0]

The first two tiles immediately break alternation. Some implementations incorrectly continue counting beyond a broken sequence. This solution resets alternating_length to 1 whenever two adjacent values match, guaranteeing correctness.

Windows Crossing the Boundary

Consider:

colors = [1,0,1,0,1]
k = 3

Several valid windows begin near the end of the array and continue at the start. Without extending the traversal using modulo arithmetic, these windows would be missed. The loop length n + k - 1 guarantees every circular window is examined.

No Valid Alternating Group

Consider:

colors = [1,1,1,1]
k = 3

Every adjacent pair is equal, so no valid group exists. The algorithm correctly keeps resetting the alternating streak and never increments the result.