# Alternating Groups I
**Difficulty:** EASY
[External](https://leetcode.com/problems/alternating-groups-i)
Canonical: https://scaleengineer.com/dsa/problems/alternating-groups-i
**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`. 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**.

Every 3 contiguous tiles in the circle with **alternating** colors (the middle tile has a different color from its **left** and **right** tiles) is called an **alternating** group.

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 = \[1,1,1\]

**Output:** 0

**Explanation:**

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

**Example 2:**

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

**Output:** 3

**Explanation:**

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

Alternating groups:

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

**Constraints:**

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

# Approaches
## Brute Force with Extended Array
This approach simplifies handling the circular nature of the tile arrangement by creating a new, larger array. We append the first two elements of the original array to its end. This allows us to iterate through the groups of three using standard linear indexing without special checks for wrap-around cases.
**Time:** O(n), where n is the number of tiles. We perform one pass to create the extended array and another pass to count the groups. · **Space:** O(n), as we create an auxiliary array of size n + 2 to store the extended sequence of colors.
**Pros:** Simpler loop logic by avoiding explicit modulo operations or conditional checks for wrap-around indices.
**Cons:** Uses extra space proportional to the input size, which is less efficient than an in-place approach.
### Explanation
This approach works by creating a temporary, extended array to handle the circular property of the tiles, which simplifies the iteration logic. By creating a new array `extendedColors` of size `n+2` and appending `colors[0]` and `colors[1]` to the end of the original `colors` array, we can treat the circular array as a linear one. We can then iterate from the second element to the `(n+1)`-th element of this new array, checking each triplet `(extendedColors[i-1], extendedColors[i], extendedColors[i+1])` for the alternating property. This avoids complex index calculations like modulo or conditional checks within the loop.

```java
class Solution {
    public int numberOfAlternatingGroups(int[] colors) {
        int n = colors.length;
        
        // Create an extended array to simplify boundary checks
        int[] extendedColors = new int[n + 2];
        for (int i = 0; i < n; i++) {
            extendedColors[i] = colors[i];
        }
        extendedColors[n] = colors[0];
        extendedColors[n+1] = colors[1];
        
        int count = 0;
        // Iterate through the original n possible middle elements
        // The window [i-1, i, i+1] in extendedColors corresponds to a group in the circle
        for (int i = 1; i <= n; i++) {
            if (extendedColors[i] != extendedColors[i - 1] && extendedColors[i] != extendedColors[i + 1]) {
                count++;
            }
        }
        
        return count;
    }
}
```
### Algorithm
*   Let `n` be the number of tiles in the `colors` array.
*   Create a new integer array, `extendedColors`, of size `n + 2`.
*   Copy the elements from the original `colors` array into `extendedColors`.
*   To handle the circularity, append the first two elements of `colors` to the end of `extendedColors`. So, `extendedColors[n]` becomes `colors[0]`, and `extendedColors[n+1]` becomes `colors[1]`.
*   Initialize a counter, `count`, to zero.
*   Iterate from `i = 1` to `n`. The element `extendedColors[i]` corresponds to the middle tile of a group. The loop covers all `n` possible groups from the original circular arrangement.
*   For each `i`, check if `extendedColors[i]` has a different color from its neighbors, `extendedColors[i-1]` and `extendedColors[i+1]`.
*   If `extendedColors[i] != extendedColors[i-1]` and `extendedColors[i] != extendedColors[i+1]`, increment the `count`.
*   After the loop completes, `count` will hold the total number of alternating groups. Return `count`.

## Optimized Single Pass with Modulo Arithmetic
This is the most efficient approach. It involves a single pass through the `colors` array. To handle the circular nature of the tiles, we use the modulo operator (`%`). This allows us to calculate the indices of the left and right neighbors for any given tile, including the ones at the boundaries of the array, without needing extra space.
**Time:** O(n), where n is the number of tiles. We iterate through the array exactly once. · **Space:** O(1), as we only use a constant amount of extra space for variables, regardless of the input size.
**Pros:** Optimal space complexity as it operates in-place, using only O(1) extra space.; Efficient time complexity with a single pass over the data.
**Cons:** The modulo arithmetic might be slightly less intuitive to read at first glance compared to a simple linear scan on an extended array.
### Explanation
Instead of using extra space, this optimal solution performs a single pass over the input array and uses mathematical properties to handle the circular arrangement. The modulo operator (`%`) is key here. For any tile at index `i`, its right neighbor is at `(i + 1) % n` and its left neighbor is at `(i + n - 1) % n`. The `+ n` in the left neighbor calculation is a common trick to ensure the result is always non-negative, as the result of `-1 % n` can be `-1` in some languages. By iterating from `i = 0` to `n-1` and applying these formulas, we can check every group of three contiguous tiles in the circle efficiently.

```java
class Solution {
    public int numberOfAlternatingGroups(int[] colors) {
        int n = colors.length;
        int alternatingGroups = 0;
        
        for (int i = 0; i < n; i++) {
            int leftColor = colors[(i + n - 1) % n];
            int middleColor = colors[i];
            int rightColor = colors[(i + 1) % n];
            
            if (middleColor != leftColor && middleColor != rightColor) {
                alternatingGroups++;
            }
        }
        
        return alternatingGroups;
    }
}
```
### Algorithm
*   Let `n` be the length of the `colors` array.
*   Initialize a counter `alternatingGroups` to 0.
*   Iterate through the array with an index `i` from `0` to `n-1`. Each `i` represents the index of the middle tile in a potential group.
*   For each `i`, calculate the indices of its neighbors in the circle.
    *   The left neighbor's index is `(i + n - 1) % n`.
    *   The right neighbor's index is `(i + 1) % n`.
*   Check if the color of the middle tile `colors[i]` is different from the colors of both its neighbors: `colors[(i + n - 1) % n]` and `colors[(i + 1) % n]`.
*   If the condition holds, it's an alternating group, so increment `alternatingGroups`.
*   After iterating through all possible middle tiles, return the total `alternatingGroups`.

# Solutions
### Java

```java
class Solution {
public
  int numberOfAlternatingGroups(int[] colors) {
    int k = 3;
    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 = 3;
    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]) -> int: k = 3 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

```