Scale Engineer

Alternating Groups II

Med
#2849Time: 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: O(1), as we only use a few variables to store the count and loop indices.1 company
Patterns
Sliding Window
Data structures
Array
Companies
Samsara

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

O(1), as we only use a few variables to store the count and loop indices.

Trade-offs

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).

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem