3208. Alternating Groups II #246
Description
Problem Number
3208
Problem Title
Alternating Groups II
LeetCode Link
https://leetcode.com/problems/alternating-groups-ii
Contribution Checklist
- I have written the Approach section.
- I have written the Intuition section.
- I have included a working C++ solution.
- I will raise a PR and ensure the filename follows the convention
[Number]. [Problem Title].cpp.
Approach
Duplicate the array so that we can handle circular sequences easily. This makes the array length 2 * n.
Use two pointers l (left) and r (right) to maintain a sliding window.
Track the last seen color using a variable (flag).
If the next color is the same as flag, it breaks the alternating pattern, so move l to r.
Otherwise, continue expanding the window.
Whenever the window size (r - l + 1) becomes k, we’ve found one valid alternating group.
Increment the count and slide l by one to check for overlapping groups.
Continue this process until all possible positions are checked within the first n elements of the doubled array.
Intuition
The main idea is to identify all contiguous subarrays (or groups) of length k that alternate between colors ; meaning no two adjacent elements are the same.
To handle circular cases , we can duplicate the array so that every possible circular group can be represented linearly.
Then, using a sliding window, we can efficiently count how many valid alternating groups of size k exist
Solution in C++
class Solution {
public:
int numberOfAlternatingGroups(vector<int>& colors, int k) {
int n = colors.size();
vector<int> arr(2 * n);
copy(colors.begin(), colors.end(), arr.begin());
copy(colors.begin(), colors.end(), arr.begin() + n);
int l = 0, r = 1, flag = colors[0], count = 0;
while (r < arr.size() && l < n) {
if (arr[r] == flag) l = r;
else flag = arr[r];
if ((r - l + 1) == k) {
count++;
l++;
}
r++;
}
return count;
}
};