Alternating Groups II

Leetcode Problem:

• Alternating Groups II

Summary

• Find the number of alternating groups in a circle of red and blue tiles

Approach

• This solution uses a circular approach to find the alternating groups
• It first extends the colors array to make it circular, then it iterates through the array in two passes: one from the start and one from the middle of the array
• In each pass, it checks for the presence of alternating groups and increments the counter if a group is found.

Complexity

• O(N) where N is the number of tiles in the circle

Explanation

• The solution works by first extending the colors array to make it circular
• This is done by adding the first element to the end of the array
• Then, it iterates through the array in two passes: one from the start and one from the middle of the array
• In each pass, it checks for the presence of alternating groups by comparing the current color with the previous color
• If the colors are alternating, it increments the counter
• Finally, it returns the counter as the number of alternating groups

Solution Code:

class Solution {
public:
    int numberOfAlternatingGroups(vector& colors, int k) {
        int N = colors.size();
        for(int i = 0 ; i < N; i++){
            colors.push_back(colors[i]);
        }
        int cnt = 1;
        int cur = colors[0] ^ 1;
        int ans = 0;
        for(int i = 1; i < k; i++){
            if(cur == colors[i]){
                cnt++;
            }else{
                cnt = 1;
            }
            cur = colors[i] ^ 1;
        }
        if(cnt >= k){
            ans++;
        }
        for(int i = k; i < N + k - 1; i++){
            if(cur == colors[i]){
                cnt++;
            }else{
                cnt = 1;
            }
            if(cnt >= k){
                ans++;
            }
            cur = colors[i] ^ 1;
        }
        return ans;
    }
};