There is a circle of red and blue tiles. You are given an array of integers colors. 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.Every 3 contiguous tiles in the circle with alternating colors (the middle tile has a different color from its left and right tiles) is called an alternating group.
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 = [1,1,1]
Output: 0
Explanation:
Example 2:
Input: colors = [0,1,0,0,1]
Output: 3
Explanation:
Alternating groups:
Constraints:
3 <= colors.length <= 1000 <= colors[i] <= 1Problem Overview: You are given a circular colors array where each value represents a tile color. A group is valid if three consecutive tiles form an alternating pattern (for example 0,1,0 or 1,0,1). Because the array is circular, the sequence can wrap from the end back to the start. The task is to count how many length-3 groups satisfy this alternating rule.
Approach 1: Iterative Pattern Check (O(n) time, O(1) space)
Iterate through every index i and examine the next two elements using circular indexing. A valid alternating group occurs when colors[i] != colors[i+1] and colors[i+1] != colors[i+2]. These two comparisons guarantee the pattern flips at each step. Use modulo arithmetic to wrap indices: (i + 1) % n and (i + 2) % n. This approach simply scans the array once, performs constant comparisons per index, and increments a counter when the condition holds. The logic is straightforward and works well when the group size is fixed.
This technique relies purely on sequential iteration over the array. Since only three values are inspected at a time, memory usage stays constant and the runtime grows linearly with the number of tiles.
Approach 2: Sliding Window (O(n) time, O(1) space)
A more general way to reason about the problem is with a fixed-size sliding window of length 3. Start with the first three elements and verify whether they alternate. Then slide the window forward by one position at a time while maintaining circular indexing. Each shift removes the leftmost element and includes the next element in the circle.
The key insight is that the window validity depends only on two adjacent comparisons: a != b and b != c. Every time the window moves, recompute these comparisons for the new triplet. Because the window size never changes, each step performs constant work. The circular property is handled by indexing with modulo so the window naturally wraps from the last element to the first.
This method is conceptually useful because it mirrors how many larger alternating-pattern problems are solved. When group sizes become variable or constraints increase, the sliding window pattern scales better than hardcoding comparisons.
Recommended for interviews: The sliding window explanation is typically preferred. Interviewers expect you to recognize the alternating constraint as a local window property and scan the array in O(n) time with constant memory. The direct iteration solution also runs in linear time and clearly demonstrates understanding, but framing it as a window problem shows stronger familiarity with common algorithm patterns.
This approach iteratively checks each possible set of three consecutive tiles (considering the circle property) to determine if they form an alternating group. By ensuring the middle tile has a different color from its adjacent tiles, we can count these groups effectively.
The code uses a loop to iterate through each tile. For each tile, it checks a group formed by the current tile and the next two, using modulo arithmetic to wrap around the array index when necessary. It checks if the middle tile is not equal to both its adjacent tiles and increments the counter if true.
Time Complexity: O(n) where n is the number of tiles.
Space Complexity: O(1) because no extra space is used except for a few variables.
This approach uses a sliding window technique to optimize the checking of three consecutive tiles by keeping track of just the current sequence of three tiles. It moves the window one tile forward at each step, efficiently checking each group and counting the valid alternating groups.
Using a variable window of size three that shifts across the circular array, the implementation ensures each pass only checks a small, bounded portion of the array. This limits the overhead of condition checks and can quickly pivot to the next group.
Time Complexity: O(n) where n is the number of tiles.
Space Complexity: O(1) because it requires no additional space beyond in-place modifications.
We set k = 3, indicating that the length of the alternating group is 3.
For convenience, 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 |
|---|---|
| Iterative Approach | Time Complexity: O(n) where n is the number of tiles. |
| Optimized Sliding Window Approach | Time Complexity: O(n) where n is the number of tiles. |
| Single Pass | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Pattern Check | O(n) | O(1) | Best when the group size is fixed (3) and you want the simplest implementation. |
| Sliding Window | O(n) | O(1) | Preferred conceptual approach for pattern detection problems and scalable to larger window sizes. |
3206 & 3208. Alternating Groups II | 3206. Alternating Groups I | Not Sliding Window • Aryan Mittal • 6,390 views views
Watch 4 more video solutions →Practice Alternating Groups I with our built-in code editor and test cases.
Practice on FleetCode