Alternating Groups II

MEDIUM

Description

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:

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 <= 10⁵
0 <= colors[i] <= 1
3 <= k <= colors.length

Approaches

Checkout 3 different approaches to solve Alternating Groups II. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

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 alternatingGroupsCount to 0.
Iterate with an index i from 0 to n-1, representing the starting tile of a group.
For each i, assume the current group is alternating by setting a flag isAlternating to true.
Start an inner loop with an index j from 0 to k-2 to check adjacent pairs within the group.
Compare colors[(i + j) % n] and colors[(i + j + 1) % n]. If they are the same, set isAlternating to false and break the inner loop.
After the inner loop, if isAlternating is still true, increment alternatingGroupsCount.
After the outer loop finishes, return alternatingGroupsCount.

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 Analysis

Time Complexity: 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 Complexity: O(1), as we only use a few variables to store the count and loop indices.

Pros and Cons

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 (k can be close to n).

Code Solutions

Checking out 3 solutions in different languages for Alternating Groups II. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Alternating Groups II

Patterns:

Sliding Window

Data Structures:

Array

Companies:

Samsara |

Alternating Groups II

Description

Approaches

Brute Force Iteration

Algorithm

Complexity Analysis

Pros and Cons

Code Solutions

Video Solution

Similar Questions

Patterns:

Data Structures:

Companies:

On this page

Subscribe to Scale Engineer newsletter