There is a circle of red and blue tiles. You are given an array of integers colors and an integer k. The color of tile i is represented by colors[i]:
colors[i] == 0 means that tile i is red.colors[i] == 1 means that tile i is blue.An alternating group is every k contiguous tiles in the circle with alternating colors (each tile in the group except the first and last one has a different color from its left and right tiles).
Return the number of alternating groups.
Note that since colors represents a circle, the first and the last tiles are considered to be next to each other.
Example 1:
Input: colors = [0,1,0,1,0], k = 3
Output: 3
Explanation:
Alternating groups:
Example 2:
Input: colors = [0,1,0,0,1,0,1], k = 6
Output: 2
Explanation:
Alternating groups:
Example 3:
Input: colors = [1,1,0,1], k = 4
Output: 0
Explanation:
Constraints:
3 <= colors.length <= 1050 <= colors[i] <= 13 <= k <= colors.lengthProblem Overview: You are given a circular array colors and an integer k. A group is valid if the k consecutive tiles form an alternating pattern, meaning every adjacent pair has different colors. Because the array is circular, groups may wrap from the end back to the start.
Approach 1: Sliding Window on Alternation Count (O(n) time, O(1) space)
This approach treats the problem as checking whether each window of size k maintains alternating neighbors. For a group of length k, there must be exactly k-1 alternating edges. Iterate through the array while maintaining a sliding window that tracks whether adjacent elements differ. Since the array is circular, iterate up to n + k positions or use modulo indexing. Each step updates the number of valid alternating edges in the current window; when the count reaches k-1, you found a valid group. This technique is common in sliding window problems where the window property can be updated incrementally instead of recomputed.
Approach 2: Pattern Recognition with Auxiliary Array (O(n) time, O(n) space)
Another way to think about the problem is to precompute whether each adjacent pair alternates. Build an auxiliary array alt where alt[i] = 1 if colors[i] != colors[(i+1) % n], otherwise 0. A valid group of size k requires k-1 consecutive ones in this array. After building the array, run a sliding window of size k-1 across the circular structure and count windows whose sum equals k-1. This separates pattern detection from counting, which makes the logic easier to reason about when working with array transformations and pattern scanning.
The key insight across both solutions is that alternating groups are defined by edges between elements, not the elements themselves. Once you track whether neighboring values differ, the problem reduces to counting stretches of valid edges. The circular nature only affects indexing, which you handle using modulo operations or by extending the traversal range.
Recommended for interviews: The sliding window approach is the expected solution. It runs in O(n) time with constant extra space and demonstrates strong understanding of window maintenance and circular traversal. The auxiliary-array method is also linear time but uses extra memory; it’s easier to reason about and can help you derive the optimal solution during an interview.
In this approach, we utilize a sliding window to evaluate each possible group of k contiguous tiles within the circle. Since the array represents a circle, special attention is required to wrap around the end of the array. The key is to check each time whether the subarray of size k has alternating colors. As we slide the window, we determine if a new k-sized subarray maintains an alternating pattern; if so, we increment our count of alternating groups.
The C solution iterates over each possible starting index in the circular array, checking if the subarray of length k has alternating colors by comparing each pair of adjacent tiles. We use modulo operations to handle the circular nature effectively within bounds.
Time Complexity: O(n * k), where n is the number of tiles.
Space Complexity: O(1).
This approach initiates by preprocessing the colors array to recognize blocks of alternating patterns and storing them into an auxiliary array. This allows faster evaluation of k-sized blocks by looking up preprocessed boundaries directly in the auxiliary array.
In C, we preprocess each tile to check if it can start a valid alternating segment, storing results in a pattern array. This array is used to speed up checking k-sized potential groups.
Time Complexity: O(n * k).
Space Complexity: O(n).
We can unfold the ring into an array of length 2n and then traverse this array from left to right. We use a variable cnt to record the current length of the alternating group. If we encounter the same color, we reset cnt to 1; otherwise, we increment cnt. If cnt \ge k and the current position i is greater than or equal to n, then we have found an alternating group, and we increment the answer by one.
After the traversal, we return the answer.
The time complexity is O(n), where n is the length of the array colors. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: O(n * k), where n is the number of tiles. Space Complexity: O(1). |
| Pattern Recognition with Auxiliary Array | Time Complexity: O(n * k). Space Complexity: O(n). |
| Single Pass | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window on Alternation Count | O(n) | O(1) | Best general solution. Efficient for large arrays and commonly expected in interviews. |
| Auxiliary Alternation Array + Sliding Window | O(n) | O(n) | Useful when separating pattern detection from counting improves clarity or debugging. |
Alternating Groups II - Leetcode 3208 - Python • NeetCodeIO • 11,774 views views
Watch 9 more video solutions →Practice Alternating Groups II with our built-in code editor and test cases.
Practice on FleetCode