3483. Alternating Groups Ii¶

LeetCode Problem View on GitHub

3483. Alternating Groups II

Medium

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] == 0 means that tile i is red.
• colors[i] == 1 means that tile i is 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:

Example 2:

Example 3:

Constraints:

• 3 <= colors.length <= 105
• 0 <= colors[i] <= 1
• 3 <= k <= colors.length

Solution¶

class Solution {
    public int numberOfAlternatingGroups(int[] colors, int k) {
        int n = colors.length, res = 0, cnt = 1;
        for (int i = 0; i < n + k - 2; ++i) {
            cnt = colors[i % n] != colors[(i + 1) % n] ? cnt + 1 : 1; 
            if(cnt >= k) res += 1;
        }
        return res;
    }
}

Complexity Analysis¶

• Time Complexity: O(?)
• Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here