3208. Alternating Groups II

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

1. Extend the Array: To handle the circular nature of the array, extend the colors array by appending the first k-1 elements to its end. This allows us to easily check for alternating groups that wrap around the end of the array.
2. Initialize Counters: - res to store the number of alternating groups. - cnt to count the length of the current alternating group.
3. 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 the cnt counter to 1. - If the cnt counter reaches k, increment the res counter as it indicates the end of an alternating group.
4. Return the Result: Finally, return the res counter, which represents the number of alternating groups of length k.

Complexity

Time Complexity

• Extending the array takes O(k).
• Iterating through the extended array takes O(n + k - 1), which simplifies to O(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 of O(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;
};