# Alternating Groups III
**Difficulty:** HARD
[External](https://leetcode.com/problems/alternating-groups-iii)
Canonical: https://scaleengineer.com/dsa/problems/alternating-groups-iii
**Data structures:** Array, Binary Indexed Tree
---
## Problem
There are some red and blue tiles arranged circularly. You are given an array of integers `colors` and a 2D integers array `queries`.

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 a contiguous subset of tiles in the circle with **alternating** colors (each tile in the group except the first and last one has a different color from its **adjacent** tiles in the group).

You have to process queries of two types:

* `queries[i] = [1, sizei]`, determine the count of **alternating** groups with size `sizei`.
* `queries[i] = [2, indexi, colori]`, change `colors[indexi]` to `colori`.

Return an array `answer` containing the results of the queries of the first type _in order_.

**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,1,0,1\], queries = \[\[2,1,0\],\[1,4\]\]

**Output:** \[2\]

**Explanation:**

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

First query:

Change `colors[1]` to 0.

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

Second query:

Count of the alternating groups with size 4:

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

**Example 2:**

**Input:** colors = \[0,0,1,0,1,1\], queries = \[\[1,3\],\[2,3,0\],\[1,5\]\]

**Output:** \[2,0\]

**Explanation:**

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

First query:

Count of the alternating groups with size 3:

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

Second query: `colors` will not change.

Third query: There is no alternating group with size 5.

**Constraints:**

* `4 <= colors.length <= 5 * 104`
* `0 <= colors[i] <= 1`
* `1 <= queries.length <= 5 * 104`
* `queries[i][0] == 1` or `queries[i][0] == 2`
* For all `i` that:  
  * `queries[i][0] == 1`: `queries[i].length == 2`, `3 <= queries[i][1] <= colors.length - 1`
  * `queries[i][0] == 2`: `queries[i].length == 3`, `0 <= queries[i][1] <= colors.length - 1`, `0 <= queries[i][2] <= 1`

# Approaches
## Brute Force
This approach directly simulates the process described in the problem for each query. For a type 1 query asking for the count of alternating groups of a specific size, it iterates through every possible starting position in the circular array. For each start position, it then checks if the subsequent `size` tiles form an alternating sequence. This check involves another loop comparing adjacent tiles. For type 2 queries, it performs a simple update on the `colors` array.
**Time:** O(Q * n * k), where `Q` is the number of queries, `n` is the number of colors, and `k` is the size in a query. In the worst case, `k` can be close to `n`, making the complexity O(Q * n^2). · **Space:** O(1) (excluding the storage for the results array).
**Pros:** Simple to understand and implement.; Requires minimal extra space.
**Cons:** Extremely inefficient for type 1 queries, leading to a Time Limit Exceeded error on larger inputs.; Repeatedly recalculates the same information for overlapping groups in different queries.
### Explanation
The brute-force method is the most straightforward way to solve the problem. It processes each query independently without any pre-computation or auxiliary data structures to speed up future queries.

For a type 1 query `[1, size]`, we iterate through all `n` possible starting positions. For each starting position `i`, we then verify if the group of tiles `colors[i], colors[(i+1)%n], ..., colors[(i+size-1)%n]` is alternating. This verification takes O(size) time. Thus, a single type 1 query takes O(n * size) time.

For a type 2 query `[2, index, color]`, the update is a direct array modification, which takes O(1) time.

```java
class Solution {
    public int[] resultsArray(int[] colors, int[][] queries) {
        java.util.List<Integer> results = new java.util.ArrayList<>();
        int n = colors.length;

        for (int[] query : queries) {
            if (query[0] == 1) {
                int size = query[1];
                int count = 0;
                for (int i = 0; i < n; i++) {
                    boolean isAlternating = true;
                    if (size > 1) {
                        for (int j = 0; j < size - 1; j++) {
                            if (colors[(i + j) % n] == colors[(i + j + 1) % n]) {
                                isAlternating = false;
                                break;
                            }
                        }
                    }
                    if (isAlternating) {
                        count++;
                    }
                }
                results.add(count);
            } else {
                int index = query[1];
                int newColor = query[2];
                colors[index] = newColor;
            }
        }

        return results.stream().mapToInt(i -> i).toArray();
    }
}
```
### Algorithm
1. For each query of type 1, `[1, size]`, initialize a counter for alternating groups to zero.
2. Iterate through each possible starting tile index `i` from `0` to `n-1`, where `n` is the number of tiles.
3. For each starting index `i`, check if the contiguous group of tiles of length `size` forms an alternating group.
4. To check for an alternating group, iterate from `j = 0` to `size-2` and verify that `colors[(i+j)%n] != colors[(i+j+1)%n]`. The modulo operator `%n` handles the circular nature of the tiles.
5. If all adjacent pairs in the group have different colors, increment the counter.
6. After checking all starting positions, the value of the counter is the result for the query.
7. For each query of type 2, `[2, index, color]`, simply update the color of the tile at the given index: `colors[index] = color`.

## Pre-computation per Query
This approach improves upon the brute-force method by introducing an intermediate representation. Instead of checking tile colors directly, we first compute a boolean array, let's call it `good`, which marks whether each adjacent pair of tiles (including the wrap-around pair) has different colors. An alternating group of size `k` is then equivalent to finding a contiguous block of `k-1` `true` values in the `good` array.

For each type 1 query, we build the `good` array from scratch and then scan it to count the blocks of `true`s. This avoids the nested loop structure of the brute-force approach for a single query, reducing its complexity.
**Time:** O(Q * n). This is an improvement but still not sufficient for the given constraints. · **Space:** O(n) for storing the `good` array for each query.
**Pros:** More efficient than the brute-force approach.; Reduces the complexity of a single query from O(n*k) to O(n).
**Cons:** Still too slow for the given constraints as it recomputes the `good` array and block counts for every type 1 query.; The O(n) work per query is the bottleneck.
### Explanation
The core idea is to transform the problem from checking colors to checking properties of adjacent pairs. We define `good[i] = (colors[i] != colors[(i+1)%n])`.

For a type 1 query `[1, k]`:
1. We build the `good` array in O(n) time.
2. We then iterate through the `good` array to find the lengths of all contiguous blocks of `true`s. To handle the circularity, we can find a `false` entry and 'unroll' the array from there, or iterate through `2n` elements while being careful not to double-count.
3. A block of `L` consecutive `true`s corresponds to an alternating sequence of `L+1` tiles. This sequence contains `L - (k-1) + 1` (or `L-k+2`) alternating groups of size `k`.
4. We sum these contributions to get the final answer. This step also takes O(n).

This makes each type 1 query O(n). Type 2 queries are still O(1).

```java
class Solution {
    public int[] resultsArray(int[] colors, int[][] queries) {
        java.util.List<Integer> results = new java.util.ArrayList<>();
        int n = colors.length;

        for (int[] query : queries) {
            if (query[0] == 1) {
                int k = query[1];
                boolean[] good = new boolean[n];
                for (int i = 0; i < n; i++) {
                    good[i] = (colors[i] != colors[(i + 1) % n]);
                }

                int totalCount = 0;
                int currentRun = 0;
                // To handle circularity, find a false point to break the circle
                int startNode = 0;
                for(int i=0; i<n; i++){
                    if(!good[i]){
                        startNode = i + 1;
                        break;
                    }
                }
                // If all are good, special case
                if(startNode == 0 && good[0]){
                    totalCount = n;
                } else {
                    for (int i = 0; i < n; i++) {
                        int idx = (startNode + i) % n;
                        if (good[idx]) {
                            currentRun++;
                        } else {
                            if (currentRun > 0) {
                                totalCount += Math.max(0, currentRun - (k - 1) + 1);
                            }
                            currentRun = 0;
                        }
                    }
                    if (currentRun > 0) {
                        totalCount += Math.max(0, currentRun - (k - 1) + 1);
                    }
                }
                results.add(totalCount);
            } else {
                colors[query[1]] = query[2];
            }
        }
        return results.stream().mapToInt(i -> i).toArray();
    }
}
```
### Algorithm
1. An alternating group of size `k` corresponds to `k-1` consecutive adjacent pairs of tiles with different colors.
2. Define a boolean array `good` of size `n`, where `good[i]` is true if `colors[i] != colors[(i+1)%n]`, and false otherwise.
3. For a type 1 query `[1, k]`, first construct this `good` array in O(n) time.
4. Traverse the circular `good` array to find all contiguous blocks of `true` values.
5. For each block of `true`s of length `L`, it can form `max(0, L - (k-1) + 1)` alternating groups of size `k`.
6. Sum these counts over all blocks to get the total for the query.
7. For a type 2 query, update the `colors` array in O(1).

## Fenwick Tree with TreeSet
This optimal approach uses advanced data structures to handle both query types efficiently. The key insight is that updates are local, but queries are global. We need a way to quickly assess the global state after a local change.

We maintain the set of 'breaks' (where adjacent colors are the same) in a `TreeSet`. These breaks define segments of alternating colors. The lengths of these segments are what determine the answer to type 1 queries. We use Fenwick Trees to maintain an aggregate of these lengths, allowing us to answer count queries quickly.

When a color is updated, at most two `good` array positions change. This may create or remove a break. We update our `TreeSet` of breaks, calculate the change in segment lengths, and propagate these changes to the Fenwick Trees. Both updates and queries can then be handled in logarithmic time.
**Time:** O(n log n + Q log n). Initialization takes O(n log n) to build the `TreeSet`. Each query and update takes O(log n). · **Space:** O(n) to store the `good` array, the `breaks` `TreeSet`, and the Fenwick Trees.
**Pros:** Highly efficient, with logarithmic time complexity for both updates and queries.; Scales well for large inputs, passing all constraints.; Maintains the state of the system incrementally, avoiding redundant calculations.
**Cons:** Significantly more complex to implement correctly, especially the logic for handling circularity and updating segments.; Higher constant factor in runtime compared to simpler approaches, though asymptotically superior.
### Explanation
This approach provides an efficient solution by maintaining the structure of alternating segments across updates.

**Data Structures:**
- `good[]`: A boolean array where `good[i]` indicates if `colors[i]` and `colors[(i+1)%n]` differ.
- `breaks`: A `java.util.TreeSet<Integer>` storing indices `i` where `good[i]` is false.
- `ftCount`, `ftSum`: Two Fenwick Trees. `ftCount` stores counts of linear segments by length, and `ftSum` stores the sum of lengths.

**Logic:**
- **Query `[1, k]`:** An alternating group of size `k` requires a run of `k-1` `true`s in the `good` array. A linear segment of `L` `true`s contains `max(0, L - k + 2)` such groups. The total count is the sum of these contributions over all segments.
  - If `breaks` is empty, the entire circle is one alternating group of length `n`. The answer is `n` (since `k <= n`).
  - Otherwise, all segments are linear. The total count is `sum_{L=k-1..n-1} count(L) * (L - k + 2)`. This can be rewritten as `(sum L*count(L)) - (k-2)*(sum count(L))`, which can be computed in O(log n) using range queries on our two Fenwick Trees.

- **Update `[2, index, color]`:** Changing `colors[index]` affects `good[index]` and `good[(index-1+n)%n]`. For each of these positions `p`:
  - If `good[p]` flips from `true` to `false`, a new break is created at `p`. This splits a larger segment into two smaller ones. We find the old segment's length using `breaks.lower(p)` and `breaks.higher(p)`, remove its contribution from the Fenwick Trees, and add the contributions of the two new, smaller segments.
  - If `good[p]` flips from `false` to `true`, a break at `p` is removed. This merges two adjacent segments. We remove their contributions and add the contribution of the new, larger merged segment.

Each update involves a few lookups in the `TreeSet` and updates to the Fenwick Trees, all taking O(log n) time.

```java
// FenwickTree class implementation is standard
class FenwickTree {
    long[] tree;
    int size;
    public FenwickTree(int size) { this.size = size; this.tree = new long[size]; }
    public void add(int i, long delta) { while (i < size) { tree[i] += delta; i += i & -i; } }
    public long query(int i) { long sum = 0; while (i > 0) { sum += tree[i]; i -= i & -i; } return sum; }
}

class Solution {
    int n;
    int[] colors;
    boolean[] good;
    java.util.TreeSet<Integer> breaks;
    FenwickTree ftCount, ftSum;

    public int[] resultsArray(int[] colors, int[][] queries) {
        this.n = colors.length;
        this.colors = colors.clone();
        this.good = new boolean[n];
        this.breaks = new java.util.TreeSet<>();
        this.ftCount = new FenwickTree(n + 2);
        this.ftSum = new FenwickTree(n + 2);

        for (int i = 0; i < n; i++) {
            good[i] = (this.colors[i] != this.colors[(i + 1) % n]);
            if (!good[i]) breaks.add(i);
        }

        if (!breaks.isEmpty()) {
            Integer first = breaks.first(), prev = breaks.last();
            for (Integer curr : breaks) {
                addSegment(getLength(prev, curr));
                prev = curr;
            }
        }

        java.util.List<Integer> resultList = new java.util.ArrayList<>();
        for (int[] q : queries) {
            if (q[0] == 1) {
                resultList.add((int) countGroups(q[1]));
            } else {
                updateColor(q[1], q[2]);
            }
        }
        return resultList.stream().mapToInt(i -> i).toArray();
    }

    private int getLength(int b1, int b2) {
        if (b1 < b2) return b2 - b1 - 1;
        return n - b1 - 1 + b2;
    }

    private void addSegment(int len) {
        if (len <= 0) return;
        ftCount.add(len + 1, 1);
        ftSum.add(len + 1, len);
    }

    private void removeSegment(int len) {
        if (len <= 0) return;
        ftCount.add(len + 1, -1);
        ftSum.add(len + 1, -len);
    }

    private long countGroups(int k) {
        if (k > n) return 0;
        if (breaks.isEmpty()) return n;
        int kPrime = k - 1;
        long totalSumL = ftSum.query(n + 1) - ftSum.query(kPrime);
        long totalCount = ftCount.query(n + 1) - ftCount.query(kPrime);
        return totalSumL - (long) (k - 2) * totalCount;
    }

    private void updateColor(int index, int newColor) {
        if (colors[index] == newColor) return;
        colors[index] = newColor;
        updateGood((index - 1 + n) % n);
        updateGood(index);
    }

    private void updateGood(int p) {
        boolean newGood = (colors[p] != colors[(p + 1) % n]);
        if (good[p] == newGood) return;
        good[p] = newGood;

        if (newGood) { // 0 -> 1: removing a break
            Integer bPrev = breaks.lower(p); if (bPrev == null) bPrev = breaks.last();
            Integer bNext = breaks.higher(p); if (bNext == null) bNext = breaks.first();
            breaks.remove(p);
            removeSegment(getLength(bPrev, p));
            removeSegment(getLength(p, bNext));
            if (breaks.isEmpty()) return; // All good now, handled by countGroups
            addSegment(getLength(bPrev, bNext));
        } else { // 1 -> 0: adding a break
            if (breaks.isEmpty()) { // Was all good
                breaks.add(p);
                addSegment(n - 1);
                return;
            }
            Integer bPrev = breaks.lower(p); if (bPrev == null) bPrev = breaks.last();
            Integer bNext = breaks.higher(p); if (bNext == null) bNext = breaks.first();
            removeSegment(getLength(bPrev, bNext));
            addSegment(getLength(bPrev, p));
            addSegment(getLength(p, bNext));
            breaks.add(p);
        }
    }
}
```
### Algorithm
1. Define `good[i]` as `true` if `colors[i] != colors[(i+1)%n]`. A point where `good[i]` is `false` is a 'break'.
2. Use a `TreeSet` to store the indices of all breaks. This allows for efficient lookup of adjacent breaks.
3. The breaks divide the circular `good` array into segments of consecutive `true`s. The length of these segments can be calculated from the indices of adjacent breaks.
4. Use two Fenwick Trees (or Binary Indexed Trees) to maintain counts of these segments. `ftCount` stores the number of segments of a certain length `L`, and `ftSum` stores the sum of `L` for all segments of length `L`.
5. **Initialization:** Build the `good` array, populate the `breaks` `TreeSet`, and initialize the Fenwick Trees based on the initial segment lengths. This takes O(n log n).
6. **Type 1 Query `[1, k]`:** If `breaks` is empty, the whole circle is alternating, so the answer is `n`. Otherwise, use the Fenwick Trees to calculate `sum_{L=k-1 to n-1} C(L) * (L - k + 2)` in O(log n) time, where `C(L)` is the count of segments of length `L`.
7. **Type 2 Query `[2, index, color]`:** An update to `colors[index]` affects `good[index]` and `good[index-1]`. If a `good` value flips, it either creates a new break or removes an existing one. This corresponds to splitting or merging segments. Update the `breaks` `TreeSet` and the Fenwick Trees accordingly. This operation takes O(log n) time.