Alternating groups ii

Array Sliding Window

59.9% acceptance

Feb 25, 2026

763

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn number_of_alternating_groups(colors: Vec<i32>, k: i32) -> i32 {
    let n = colors.len();
    let k = k as usize;
    // Extend array by k-1 to handle wrap-around
    let mut extended = colors.clone();
    extended.extend_from_slice(&colors[..k - 1]);
    // cons[i] = length of consecutive alternating run ending at i
    let mut cons = vec![0usize; n + k - 1];
    for i in 1..n + k - 1 {
      if extended[i] != extended[i - 1] {
        cons[i] = cons[i - 1] + 1;
      } else {
        cons[i] = 0;
      }
    }
    // A window starting at i (0..n) of size k needs k-1 consecutive alternating pairs
    let mut count = 0i32;
    for i in 0..n {
      if cons[i + k - 1] >= k - 1 {
        count += 1;
      }
    }
    count
  }
}