Alternating Groups I
EasyPrompt
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] == 0means that tileiis red.colors[i] == 1means that tileiis 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] <= 1
Approaches
2 approaches with complexity analysis and trade-offs.
This approach simplifies handling the circular nature of the tile arrangement by creating a new, larger array. We append the first two elements of the original array to its end. This allows us to iterate through the groups of three using standard linear indexing without special checks for wrap-around cases.
Algorithm
- Let
nbe the number of tiles in thecolorsarray. - Create a new integer array,
extendedColors, of sizen + 2. - Copy the elements from the original
colorsarray intoextendedColors. - To handle the circularity, append the first two elements of
colorsto the end ofextendedColors. So,extendedColors[n]becomescolors[0], andextendedColors[n+1]becomescolors[1]. - Initialize a counter,
count, to zero. - Iterate from
i = 1ton. The elementextendedColors[i]corresponds to the middle tile of a group. The loop covers allnpossible groups from the original circular arrangement. - For each
i, check ifextendedColors[i]has a different color from its neighbors,extendedColors[i-1]andextendedColors[i+1]. - If
extendedColors[i] != extendedColors[i-1]andextendedColors[i] != extendedColors[i+1], increment thecount. - After the loop completes,
countwill hold the total number of alternating groups. Returncount.
Walkthrough
This approach works by creating a temporary, extended array to handle the circular property of the tiles, which simplifies the iteration logic. By creating a new array extendedColors of size n+2 and appending colors[0] and colors[1] to the end of the original colors array, we can treat the circular array as a linear one. We can then iterate from the second element to the (n+1)-th element of this new array, checking each triplet (extendedColors[i-1], extendedColors[i], extendedColors[i+1]) for the alternating property. This avoids complex index calculations like modulo or conditional checks within the loop.
class Solution { public int numberOfAlternatingGroups(int[] colors) { int n = colors.length; // Create an extended array to simplify boundary checks int[] extendedColors = new int[n + 2]; for (int i = 0; i < n; i++) { extendedColors[i] = colors[i]; } extendedColors[n] = colors[0]; extendedColors[n+1] = colors[1]; int count = 0; // Iterate through the original n possible middle elements // The window [i-1, i, i+1] in extendedColors corresponds to a group in the circle for (int i = 1; i <= n; i++) { if (extendedColors[i] != extendedColors[i - 1] && extendedColors[i] != extendedColors[i + 1]) { count++; } } return count; }}Complexity
Time
O(n), where n is the number of tiles. We perform one pass to create the extended array and another pass to count the groups.
Space
O(n), as we create an auxiliary array of size n + 2 to store the extended sequence of colors.
Trade-offs
Pros
Simpler loop logic by avoiding explicit modulo operations or conditional checks for wrap-around indices.
Cons
Uses extra space proportional to the input size, which is less efficient than an in-place approach.
This is the most efficient approach. It involves a single pass through the colors array. To handle the circular nature of the tiles, we use the modulo operator (%). This allows us to calculate the indices of the left and right neighbors for any given tile, including the ones at the boundaries of the array, without needing extra space.
Algorithm
- Let
nbe the length of thecolorsarray. - Initialize a counter
alternatingGroupsto 0. - Iterate through the array with an index
ifrom0ton-1. Eachirepresents the index of the middle tile in a potential group. - For each
i, calculate the indices of its neighbors in the circle.- The left neighbor's index is
(i + n - 1) % n. - The right neighbor's index is
(i + 1) % n.
- The left neighbor's index is
- Check if the color of the middle tile
colors[i]is different from the colors of both its neighbors:colors[(i + n - 1) % n]andcolors[(i + 1) % n]. - If the condition holds, it's an alternating group, so increment
alternatingGroups. - After iterating through all possible middle tiles, return the total
alternatingGroups.
Walkthrough
Instead of using extra space, this optimal solution performs a single pass over the input array and uses mathematical properties to handle the circular arrangement. The modulo operator (%) is key here. For any tile at index i, its right neighbor is at (i + 1) % n and its left neighbor is at (i + n - 1) % n. The + n in the left neighbor calculation is a common trick to ensure the result is always non-negative, as the result of -1 % n can be -1 in some languages. By iterating from i = 0 to n-1 and applying these formulas, we can check every group of three contiguous tiles in the circle efficiently.
class Solution { public int numberOfAlternatingGroups(int[] colors) { int n = colors.length; int alternatingGroups = 0; for (int i = 0; i < n; i++) { int leftColor = colors[(i + n - 1) % n]; int middleColor = colors[i]; int rightColor = colors[(i + 1) % n]; if (middleColor != leftColor && middleColor != rightColor) { alternatingGroups++; } } return alternatingGroups; }}Complexity
Time
O(n), where n is the number of tiles. We iterate through the array exactly once.
Space
O(1), as we only use a constant amount of extra space for variables, regardless of the input size.
Trade-offs
Pros
Optimal space complexity as it operates in-place, using only O(1) extra space.
Efficient time complexity with a single pass over the data.
Cons
The modulo arithmetic might be slightly less intuitive to read at first glance compared to a simple linear scan on an extended array.
Solutions
Solution
class Solution {public int numberOfAlternatingGroups(int[] colors) { int k = 3; int n = colors.length; int ans = 0, cnt = 0; for (int i = 0; i < n << 1; ++i) { if (i > 0 && colors[i % n] == colors[(i - 1) % n]) { cnt = 1; } else { ++cnt; } ans += i >= n && cnt >= k ? 1 : 0; } return ans; }}class Solution {public: int numberOfAlternatingGroups(vector<int> &colors) { int k = 3; int n = colors.size(); int ans = 0, cnt = 0; for (int i = 0; i < n << 1; ++i) { if (i && colors[i % n] == colors[(i - 1) % n]) { cnt = 1; } else { ++cnt; } ans += i >= n && cnt >= k ? 1 : 0; } return ans; }};class Solution: def numberOfAlternatingGroups(self, colors: List[int]) -> int: k = 3 n = len(colors) ans = cnt = 0 for i in range(n << 1): if i and colors[i % n] == colors[(i - 1) % n]: cnt = 1 else: cnt += 1 ans += i >= n and cnt >= k return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.