Alternating Groups II
MedPrompt
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] == 0means that tileiis red.colors[i] == 1means that tileiis 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.length
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward approach is to check every possible contiguous group of k tiles. We iterate through each possible starting index i from 0 to n-1, where n is the number of tiles. For each starting index, we then check if the subsequent k-1 tiles form an alternating color pattern. To handle the circular nature of the tiles, we use the modulo operator (%) to wrap around the array indices.
Algorithm
- Initialize a counter
alternatingGroupsCountto 0. - Iterate with an index
ifrom0ton-1, representing the starting tile of a group. - For each
i, assume the current group is alternating by setting a flagisAlternatingtotrue. - Start an inner loop with an index
jfrom0tok-2to check adjacent pairs within the group. - Compare
colors[(i + j) % n]andcolors[(i + j + 1) % n]. If they are the same, setisAlternatingtofalseand break the inner loop. - After the inner loop, if
isAlternatingis stilltrue, incrementalternatingGroupsCount. - After the outer loop finishes, return
alternatingGroupsCount.
Walkthrough
We can implement this by using two nested loops. The outer loop selects the starting tile of a potential group, and the inner loop verifies the alternating color condition for all k tiles in that group.
public class Solution { public int numberOfAlternatingGroups(int[] colors, int k) { int n = colors.length; if (k > n) { return 0; } int count = 0; for (int i = 0; i < n; i++) { boolean isAlternating = true; for (int j = 0; j < k - 1; j++) { int currentIdx = (i + j) % n; int nextIdx = (i + j + 1) % n; if (colors[currentIdx] == colors[nextIdx]) { isAlternating = false; break; } } if (isAlternating) { count++; } } return count; }}The code iterates through all n possible starting positions. For each start, it checks k-1 pairs, leading to a total of n * (k-1) comparisons in the worst case.
Complexity
Time
O(n * k), where `n` is the length of `colors`. For each of the `n` starting positions, we perform up to `k-1` comparisons.
Space
O(1), as we only use a few variables to store the count and loop indices.
Trade-offs
Pros
Very simple to understand and implement.
Requires no extra space.
Cons
Highly inefficient and will likely result in a 'Time Limit Exceeded' error for large inputs, as the complexity is quadratic in the worst case (
kcan be close ton).
To improve upon the brute-force method, we can avoid redundant checks. The key observation is that an alternating group of size k is simply a part of a longer alternating sequence. We can first find the lengths of all maximal alternating sequences. To simplify handling the circularity, we can create a temporary extended array. Then, we can determine the number of valid groups based on the lengths of these sequences.
Algorithm
- Create a new array
extendedColorsof sizen + k - 1. - Copy
colorsinto the firstnpositions ofextendedColors. - Copy the first
k-1elements ofcolorsinto the lastk-1positions ofextendedColors. - Create an integer array
altLengthsof sizen + k - 1. - Initialize
altLengths[0] = 1. - Iterate
ifrom1ton + k - 2. IfextendedColors[i] != extendedColors[i-1], setaltLengths[i] = altLengths[i-1] + 1. Otherwise, resetaltLengths[i] = 1. - Initialize
count = 0. - Iterate
ifromk-1ton + k - 2. IfaltLengths[i] >= k, incrementcount. - Return
count.
Walkthrough
This method involves three main steps: extending the array to handle circularity, computing the lengths of alternating sequences, and then counting the valid groups.
- Extend Array: We create a new array of size
n + k - 1by appending the firstk-1elements of the originalcolorsarray to its end. This transforms the circular problem into a linear one for any window of sizek. - Compute Alternating Lengths: We create another array,
altLengths, wherealtLengths[i]stores the length of the alternating sequence ending at indexiof the extended array. - Count Groups: A window of size
kending at indexiis alternating if and only ifaltLengths[i] >= k. We can iterate throughaltLengthsand count how many times this condition is met.
public class Solution { public int numberOfAlternatingGroups(int[] colors, int k) { int n = colors.length; if (k > n) { return 0; } int[] extendedColors = new int[n + k - 1]; System.arraycopy(colors, 0, extendedColors, 0, n); System.arraycopy(colors, 0, extendedColors, n, k - 1); int[] altLengths = new int[n + k - 1]; altLengths[0] = 1; for (int i = 1; i < n + k - 1; i++) { if (extendedColors[i] != extendedColors[i - 1]) { altLengths[i] = altLengths[i - 1] + 1; } else { altLengths[i] = 1; } } int count = 0; for (int i = k - 1; i < n + k - 1; i++) { if (altLengths[i] >= k) { count++; } } return count; }}Complexity
Time
O(n + k), which simplifies to O(n) since `k <= n`. Each step (extending array, computing lengths, counting) takes linear time.
Space
O(n + k), which simplifies to O(n). We use two auxiliary arrays whose sizes depend on `n` and `k`.
Trade-offs
Pros
Significantly more efficient than the brute-force approach.
The logic of transforming a circular problem to a linear one is a useful pattern.
Cons
Requires extra space proportional to
n+k, which might be a concern for very large inputs or strict memory constraints.
This approach is the most optimal, achieving linear time complexity with constant extra space. It refines the sliding window concept by eliminating the need for auxiliary arrays. We can iterate through the elements once, conceptually treating the array as circular, and maintain the length of the current alternating sequence. A valid group is found whenever this length reaches k.
Algorithm
- Initialize
count = 0andcurrentLength = 1. - Iterate with an index
ifrom1ton + k - 2. This range covers allnunique windows of sizekin the circular array. - Inside the loop, compare
colors[i % n]withcolors[(i - 1) % n]. - If the colors are different, increment
currentLength. - If the colors are the same, reset
currentLengthto1. - After updating
currentLength, check ifcurrentLength >= k. If it is, incrementcount. - After the loop, return
count.
Walkthrough
We use a single loop that runs for n + k - 2 iterations to cover all n possible circular groups of size k. A variable, currentLength, tracks the length of the alternating sequence ending at the current position.
When we move from index i-1 to i, if the colors colors[(i-1)%n] and colors[i%n] are different, we extend the current alternating sequence. Otherwise, the sequence is broken and starts over from the current element.
Each time the currentLength becomes k or more, it signifies that the window of size k ending at the current position is an alternating group, so we increment our result counter.
public class Solution { public int numberOfAlternatingGroups(int[] colors, int k) { int n = colors.length; int count = 0; int currentLength = 1; // We iterate up to n + k - 2 to check all n windows of size k. // The loop runs from i=1 to n+k-2, which is n+k-2 times. for (int i = 1; i < n + k - 1; i++) { if (colors[i % n] != colors[(i - 1) % n]) { currentLength++; } else { currentLength = 1; } // If the current alternating sequence has length at least k, // the window of size k ending at the current position is a valid group. if (currentLength >= k) { count++; } } return count; }}This single loop effectively slides a window across the circular array, updating the count in one pass.
Complexity
Time
O(n + k), which simplifies to O(n) as `k <= n`. We perform a single pass of length `n + k - 1`.
Space
O(1). We only use a few variables to keep track of the count and current sequence length, regardless of the input size.
Trade-offs
Pros
Optimal solution with linear time and constant space complexity.
Efficient for all input sizes within the given constraints.
Cons
The logic of iterating
n + k - 1times with modulo arithmetic might be slightly less intuitive at first glance compared to the other approaches.
Solutions
Solution
class Solution {public int numberOfAlternatingGroups(int[] colors, int k) { 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) { 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], k: int) -> int: 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.