🎨Now live: Try our Free AI Image Generation Feature

Intuition
The problem requires us to find the number of alternating groups of length k
in a circular array of tiles, where each tile is either red or blue. An alternating group is defined as a contiguous sequence of k
tiles in which each tile, except the first and last one, alternates colors with its neighboring tiles. Since the array represents a circle, the first and last tiles are considered adjacent.
Approach
- Extend the Array: To handle the circular nature of the array, extend the
colors
array by appending the firstk-1
elements to its end. This allows us to easily check for alternating groups that wrap around the end of the array. - Initialize Counters:
-
res
to store the number of alternating groups. -cnt
to count the length of the current alternating group. - Iterate Through the Extended Array:
- For each tile, check if its color is different from the previous tile.
- If it is, increment the
cnt
counter. - If it isn't, reset thecnt
counter to 1. - If thecnt
counter reachesk
, increment theres
counter as it indicates the end of an alternating group. - Return the Result: Finally, return the
res
counter, which represents the number of alternating groups of lengthk
.
Complexity
Time Complexity
- Extending the array takes
O(k)
. - Iterating through the extended array takes
O(n + k - 1)
, which simplifies toO(n + k)
.
Therefore, the overall time complexity is O(n + k)
.
Space Complexity
- Extending the array requires additional space for
k-1
elements, resulting in a space complexity ofO(n + k)
.
Therefore, the overall space complexity is O(n + k)
.
Code
C++
class Solution {
public:
int numberOfAlternatingGroups(vector& colors, int k) {
for (int i = 0; i < k - 1; ++i) colors.push_back(colors[i]);
int res = 0;
int cnt = 1;
for (int i = 1; i < colors.size(); ++i) {
if (colors[i] != colors[i - 1]) ++cnt;
else cnt = 1;
if (cnt >= k) ++res;
}
return res;
}
};
Python
class Solution:
def numberOfAlternatingGroups(self, colors: List[int], k: int) -> int:
n = len(colors)
colors += colors[:k - 1]
res = 0
cnt = 1
for i in range(1, len(colors)):
if colors[i] != colors[i - 1]:
cnt += 1
else:
cnt = 1
if cnt >= k:
res += 1
return res
Java
class Solution {
public int numberOfAlternatingGroups(int[] colors, int k) {
int n = colors.length;
int[] extendedColors = new int[n + k - 1];
System.arraycopy(colors, 0, extendedColors, 0, n);
System.arraycopy(colors, 0, extendedColors, n, k - 1);
int res = 0;
int cnt = 1;
for (int i = 1; i < extendedColors.length; ++i) {
if (extendedColors[i] != extendedColors[i - 1]) ++cnt;
else cnt = 1;
if (cnt >= k) ++res;
}
return res;
}
}
JavaScript
/**
* @param {number[]} colors
* @param {number} k
* @return {number}
*/
var numberOfAlternatingGroups = function (colors, k) {
for (var i = 0; i < k - 1; ++i) colors.push(colors[i]);
var res = 0;
var cnt = 1;
for (var i = 1; i < colors.length; ++i) {
if (colors[i] !== colors[i - 1]) ++cnt;
else cnt = 1;
if (cnt >= k) ++res;
}
return res;
};