Alternating Groups II

medium array sliding window circular

Problem

A circle of tiles is given by an array colors, where 0 is red and 1 is blue. Because the tiles form a circle, the first and last tiles are neighbors. An alternating group is a block of k contiguous tiles whose colors strictly alternate — every tile inside the block (all but the two ends) differs from both its left and right neighbor. Count how many alternating groups exist.

Inputcolors = [0,1,0,1,0], k = 3

Output3

The length-3 windows starting at indices 0, 1 and 2 each alternate (0,1,0 / 1,0,1 / 0,1,0). The windows wrapping past the end fail, so the answer is 3.

colors (comma-separated 0/1)

def numberOfAlternatingGroups(colors, k):
    n = len(colors)
    ans = 0
    length = 1                       # current run of alternating tiles
    # walk i around the circle; n + k - 1 covers every wrapping window
    for i in range(1, n + k - 1):
        if colors[i % n] != colors[(i - 1) % n]:
            length += 1              # color flipped, extend the run
        else:
            length = 1               # equal neighbors break the run
        if length >= k:
            ans += 1                 # a length-k alternating window ends at i
    return ans

function numberOfAlternatingGroups(colors, k) {
  const n = colors.length;
  let ans = 0;
  let length = 1;                       // current run of alternating tiles
  // walk i around the circle; n + k - 1 covers every wrapping window
  for (let i = 1; i < n + k - 1; i++) {
    if (colors[i % n] !== colors[(i - 1) % n]) {
      length += 1;                      // color flipped, extend the run
    } else {
      length = 1;                       // equal neighbors break the run
    }
    if (length >= k) {
      ans += 1;                         // a length-k alternating window ends at i
    }
  }
  return ans;
}

int numberOfAlternatingGroups(int[] colors, int k) {
    int n = colors.length;
    int ans = 0;
    int length = 1;                      // current run of alternating tiles
    // walk i around the circle; n + k - 1 covers every wrapping window
    for (int i = 1; i < n + k - 1; i++) {
        if (colors[i % n] != colors[(i - 1) % n]) {
            length += 1;                 // color flipped, extend the run
        } else {
            length = 1;                  // equal neighbors break the run
        }
        if (length >= k) {
            ans += 1;                    // a length-k alternating window ends at i
        }
    }
    return ans;
}

int numberOfAlternatingGroups(vector<int>& colors, int k) {
    int n = colors.size();
    int ans = 0;
    int length = 1;                      // current run of alternating tiles
    // walk i around the circle; n + k - 1 covers every wrapping window
    for (int i = 1; i < n + k - 1; i++) {
        if (colors[i % n] != colors[(i - 1) % n]) {
            length += 1;                 // color flipped, extend the run
        } else {
            length = 1;                  // equal neighbors break the run
        }
        if (length >= k) {
            ans += 1;                    // a length-k alternating window ends at i
        }
    }
    return ans;
}

Explanation

A window of k tiles is an alternating group exactly when every adjacent pair inside it has different colors. So instead of re-checking each window from scratch, we sweep around the circle once and keep a running length — how many tiles in a row have alternated up to the current position.

At each index i we compare colors[i] with its previous tile colors[i-1]. If they differ, the alternating run grows by one (length += 1). If they are equal, the run is broken and we restart it at length = 1 (the single tile i always starts a fresh run of length 1).

Whenever length reaches k or more, the last k tiles ending at i form a valid alternating group, so we add one to ans. Because the run length is capped only by how far it has grown, each ending position contributes at most one window — exactly the window of size k that ends there.

To handle the circle, we let i run from 1 to n + k - 2 and index with i % n. The extra k - 1 steps past the end let windows that wrap from the tail back to the head be counted, while never counting the same window twice.

For colors = [0,1,0,1,0], k = 3 the run grows the whole way (every neighbor flips) until the wrap reaches two equal tiles, giving the three windows starting at indices 0, 1 and 2 — answer 3.

Time: O(n + k) Space: O(1)