# Alternating Groups II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/alternating-groups-ii)
Canonical: https://scaleengineer.com/dsa/problems/alternating-groups-ii
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** Array
**Companies:** [Samsara](https://scaleengineer.com/companies/samsara)
---
## Problem
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:**

**![](https://assets.glich.co/dsa/alternating-groups-ii/image0.png)**

Alternating groups:

![](https://assets.glich.co/dsa/alternating-groups-ii/image1.png)![](https://assets.glich.co/dsa/alternating-groups-ii/image2.png)![](https://assets.glich.co/dsa/alternating-groups-ii/image3.png)

**Example 2:**

**Input:** colors = \[0,1,0,0,1,0,1\], k = 6

**Output:** 2

**Explanation:**

**![](https://assets.glich.co/dsa/alternating-groups-ii/image4.png)**

Alternating groups:

![](https://assets.glich.co/dsa/alternating-groups-ii/image5.png)![](https://assets.glich.co/dsa/alternating-groups-ii/image6.png)

**Example 3:**

**Input:** colors = \[1,1,0,1\], k = 4

**Output:** 0

**Explanation:**

![](https://assets.glich.co/dsa/alternating-groups-ii/image7.png)

**Constraints:**

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

# Approaches
## 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.
**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.
**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`).
### Explanation
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.
```java
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.
### 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`.

## Sliding Window with Pre-computation
To improve upon the brute-force method, we can avoid redundant checks. The key observation is that an alternating group of size `k` is simply a part of a longer alternating sequence. We can first find the lengths of all maximal alternating sequences. To simplify handling the circularity, we can create a temporary extended array. Then, we can determine the number of valid groups based on the lengths of these sequences.
**Time:** O(n + k), which simplifies to O(n) since `k <= n`. Each step (extending array, computing lengths, counting) takes linear time. · **Space:** O(n + k), which simplifies to O(n). We use two auxiliary arrays whose sizes depend on `n` and `k`.
**Pros:** Significantly more efficient than the brute-force approach.; The logic of transforming a circular problem to a linear one is a useful pattern.
**Cons:** Requires extra space proportional to `n+k`, which might be a concern for very large inputs or strict memory constraints.
### Explanation
This method involves three main steps: extending the array to handle circularity, computing the lengths of alternating sequences, and then counting the valid groups.
1.  **Extend Array**: We create a new array of size `n + k - 1` by appending the first `k-1` elements of the original `colors` array to its end. This transforms the circular problem into a linear one for any window of size `k`.
2.  **Compute Alternating Lengths**: We create another array, `altLengths`, where `altLengths[i]` stores the length of the alternating sequence ending at index `i` of the extended array.
3.  **Count Groups**: A window of size `k` ending at index `i` is alternating if and only if `altLengths[i] >= k`. We can iterate through `altLengths` and count how many times this condition is met.
```java
public class Solution {
    public int numberOfAlternatingGroups(int[] colors, int k) {
        int n = colors.length;
        if (k > n) {
            return 0;
        }
        
        int[] extendedColors = new int[n + k - 1];
        System.arraycopy(colors, 0, extendedColors, 0, n);
        System.arraycopy(colors, 0, extendedColors, n, k - 1);
        
        int[] altLengths = new int[n + k - 1];
        altLengths[0] = 1;
        for (int i = 1; i < n + k - 1; i++) {
            if (extendedColors[i] != extendedColors[i - 1]) {
                altLengths[i] = altLengths[i - 1] + 1;
            } else {
                altLengths[i] = 1;
            }
        }
        
        int count = 0;
        for (int i = k - 1; i < n + k - 1; i++) {
            if (altLengths[i] >= k) {
                count++;
            }
        }
        
        return count;
    }
}
```
### Algorithm
- Create a new array `extendedColors` of size `n + k - 1`.
- Copy `colors` into the first `n` positions of `extendedColors`.
- Copy the first `k-1` elements of `colors` into the last `k-1` positions of `extendedColors`.
- Create an integer array `altLengths` of size `n + k - 1`.
- Initialize `altLengths[0] = 1`.
- Iterate `i` from `1` to `n + k - 2`. If `extendedColors[i] != extendedColors[i-1]`, set `altLengths[i] = altLengths[i-1] + 1`. Otherwise, reset `altLengths[i] = 1`.
- Initialize `count = 0`.
- Iterate `i` from `k-1` to `n + k - 2`. If `altLengths[i] >= k`, increment `count`.
- Return `count`.

## Optimized Sliding Window in a Single Pass
This approach is the most optimal, achieving linear time complexity with constant extra space. It refines the sliding window concept by eliminating the need for auxiliary arrays. We can iterate through the elements once, conceptually treating the array as circular, and maintain the length of the current alternating sequence. A valid group is found whenever this length reaches `k`.
**Time:** O(n + k), which simplifies to O(n) as `k <= n`. We perform a single pass of length `n + k - 1`. · **Space:** O(1). We only use a few variables to keep track of the count and current sequence length, regardless of the input size.
**Pros:** Optimal solution with linear time and constant space complexity.; Efficient for all input sizes within the given constraints.
**Cons:** The logic of iterating `n + k - 1` times with modulo arithmetic might be slightly less intuitive at first glance compared to the other approaches.
### Explanation
We use a single loop that runs for `n + k - 2` iterations to cover all `n` possible circular groups of size `k`. A variable, `currentLength`, tracks the length of the alternating sequence ending at the current position.
When we move from index `i-1` to `i`, if the colors `colors[(i-1)%n]` and `colors[i%n]` are different, we extend the current alternating sequence. Otherwise, the sequence is broken and starts over from the current element.
Each time the `currentLength` becomes `k` or more, it signifies that the window of size `k` ending at the current position is an alternating group, so we increment our result counter.
```java
public class Solution {
    public int numberOfAlternatingGroups(int[] colors, int k) {
        int n = colors.length;
        int count = 0;
        int currentLength = 1;

        // We iterate up to n + k - 2 to check all n windows of size k.
        // The loop runs from i=1 to n+k-2, which is n+k-2 times.
        for (int i = 1; i < n + k - 1; i++) {
            if (colors[i % n] != colors[(i - 1) % n]) {
                currentLength++;
            } else {
                currentLength = 1;
            }
            
            // If the current alternating sequence has length at least k,
            // the window of size k ending at the current position is a valid group.
            if (currentLength >= k) {
                count++;
            }
        }
        return count;
    }
}
```
This single loop effectively slides a window across the circular array, updating the count in one pass.
### Algorithm
- Initialize `count = 0` and `currentLength = 1`.
- Iterate with an index `i` from `1` to `n + k - 2`. This range covers all `n` unique windows of size `k` in the circular array.
- Inside the loop, compare `colors[i % n]` with `colors[(i - 1) % n]`.
- If the colors are different, increment `currentLength`.
- If the colors are the same, reset `currentLength` to `1`.
- After updating `currentLength`, check if `currentLength >= k`. If it is, increment `count`.
- After the loop, return `count`.

# Solutions
### Java

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

```

### CPP

```cpp
class Solution {
public:
  int numberOfAlternatingGroups(vector<int> &colors, int k) {
    int n = colors.size();
    int ans = 0, cnt = 0;
    for (int i = 0; i < n << 1; ++i) {
      if (i && colors[i % n] == colors[(i - 1) % n]) {
        cnt = 1;
      } else {
        ++cnt;
      }
      ans += i >= n && cnt >= k ? 1 : 0;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def numberOfAlternatingGroups(self, colors: List[int], k: int) -> int: n = len(colors) ans = cnt = 0 for i in range(n << 1): if i and colors[i % n] == colors[(i - 1) % n]: cnt = 1 else: cnt += 1 ans += i >= n and cnt >= k return ans

```