Alternating Groups III

Hard

#2882Time: 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).

Data structures

Array Binary Indexed Tree

Prompt

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, size_i], determine the count of alternating groups with size size_i.
queries[i] = [2, index_i, color_i], change colors[index_i] to color_i.

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:

First query:

Change colors[1] to 0.

Second query:

Count of the alternating groups with size 4:

Example 2:

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

Output: [2,0]

Explanation:

First query:

Count of the alternating groups with size 3:

Second query: colors will not change.

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

Constraints:

4 <= colors.length <= 5 * 10⁴
0 <= colors[i] <= 1
1 <= queries.length <= 5 * 10⁴
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

3 approaches with complexity analysis and trade-offs.

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.

Algorithm

For each query of type 1, [1, size], initialize a counter for alternating groups to zero.
Iterate through each possible starting tile index i from 0 to n-1, where n is the number of tiles.
For each starting index i, check if the contiguous group of tiles of length size forms an alternating group.
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.
If all adjacent pairs in the group have different colors, increment the counter.
After checking all starting positions, the value of the counter is the result for the query.
For each query of type 2, [2, index, color], simply update the color of the tile at the given index: colors[index] = color.

Walkthrough

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.

1class Solution {2    public int[] resultsArray(int[] colors, int[][] queries) {3        java.util.List<Integer> results = new java.util.ArrayList<>();4        int n = colors.length;5 6        for (int[] query : queries) {7            if (query[0] == 1) {8                int size = query[1];9                int count = 0;10                for (int i = 0; i < n; i++) {11                    boolean isAlternating = true;12                    if (size > 1) {13                        for (int j = 0; j < size - 1; j++) {14                            if (colors[(i + j) % n] == colors[(i + j + 1) % n]) {15                                isAlternating = false;16                                break;17                            }18                        }19                    }20                    if (isAlternating) {21                        count++;22                    }23                }24                results.add(count);25            } else {26                int index = query[1];27                int newColor = query[2];28                colors[index] = newColor;29            }30        }31 32        return results.stream().mapToInt(i -> i).toArray();33    }34}

Complexity

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).

Trade-offs

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.

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 trues. This avoids the nested loop structure of the brute-force approach for a single query, reducing its complexity.

Algorithm

An alternating group of size k corresponds to k-1 consecutive adjacent pairs of tiles with different colors.
Define a boolean array good of size n, where good[i] is true if colors[i] != colors[(i+1)%n], and false otherwise.
For a type 1 query [1, k], first construct this good array in O(n) time.
Traverse the circular good array to find all contiguous blocks of true values.
For each block of trues of length L, it can form max(0, L - (k-1) + 1) alternating groups of size k.
Sum these counts over all blocks to get the total for the query.
For a type 2 query, update the colors array in O(1).

Walkthrough

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]:

We build the good array in O(n) time.
We then iterate through the good array to find the lengths of all contiguous blocks of trues. 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.
A block of L consecutive trues 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.
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).

1class Solution {2    public int[] resultsArray(int[] colors, int[][] queries) {3        java.util.List<Integer> results = new java.util.ArrayList<>();4        int n = colors.length;5 6        for (int[] query : queries) {7            if (query[0] == 1) {8                int k = query[1];9                boolean[] good = new boolean[n];10                for (int i = 0; i < n; i++) {11                    good[i] = (colors[i] != colors[(i + 1) % n]);12                }13 14                int totalCount = 0;15                int currentRun = 0;16                // To handle circularity, find a false point to break the circle17                int startNode = 0;18                for(int i=0; i<n; i++){19                    if(!good[i]){20                        startNode = i + 1;21                        break;22                    }23                }24                // If all are good, special case25                if(startNode == 0 && good[0]){26                    totalCount = n;27                } else {28                    for (int i = 0; i < n; i++) {29                        int idx = (startNode + i) % n;30                        if (good[idx]) {31                            currentRun++;32                        } else {33                            if (currentRun > 0) {34                                totalCount += Math.max(0, currentRun - (k - 1) + 1);35                            }36                            currentRun = 0;37                        }38                    }39                    if (currentRun > 0) {40                        totalCount += Math.max(0, currentRun - (k - 1) + 1);41                    }42                }43                results.add(totalCount);44            } else {45                colors[query[1]] = query[2];46            }47        }48        return results.stream().mapToInt(i -> i).toArray();49    }50}

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.

Trade-offs

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.

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.

Algorithm

Define good[i] as true if colors[i] != colors[(i+1)%n]. A point where good[i] is false is a 'break'.
Use a TreeSet to store the indices of all breaks. This allows for efficient lookup of adjacent breaks.
The breaks divide the circular good array into segments of consecutive trues. The length of these segments can be calculated from the indices of adjacent breaks.
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.
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).
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.
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.

Walkthrough

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 trues in the good array. A linear segment of L trues 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.

1// FenwickTree class implementation is standard2class FenwickTree {3    long[] tree;4    int size;5    public FenwickTree(int size) { this.size = size; this.tree = new long[size]; }6    public void add(int i, long delta) { while (i < size) { tree[i] += delta; i += i & -i; } }7    public long query(int i) { long sum = 0; while (i > 0) { sum += tree[i]; i -= i & -i; } return sum; }8}9 10class Solution {11    int n;12    int[] colors;13    boolean[] good;14    java.util.TreeSet<Integer> breaks;15    FenwickTree ftCount, ftSum;16 17    public int[] resultsArray(int[] colors, int[][] queries) {18        this.n = colors.length;19        this.colors = colors.clone();20        this.good = new boolean[n];21        this.breaks = new java.util.TreeSet<>();22        this.ftCount = new FenwickTree(n + 2);23        this.ftSum = new FenwickTree(n + 2);24 25        for (int i = 0; i < n; i++) {26            good[i] = (this.colors[i] != this.colors[(i + 1) % n]);27            if (!good[i]) breaks.add(i);28        }29 30        if (!breaks.isEmpty()) {31            Integer first = breaks.first(), prev = breaks.last();32            for (Integer curr : breaks) {33                addSegment(getLength(prev, curr));34                prev = curr;35            }36        }37 38        java.util.List<Integer> resultList = new java.util.ArrayList<>();39        for (int[] q : queries) {40            if (q[0] == 1) {41                resultList.add((int) countGroups(q[1]));42            } else {43                updateColor(q[1], q[2]);44            }45        }46        return resultList.stream().mapToInt(i -> i).toArray();47    }48 49    private int getLength(int b1, int b2) {50        if (b1 < b2) return b2 - b1 - 1;51        return n - b1 - 1 + b2;52    }53 54    private void addSegment(int len) {55        if (len <= 0) return;56        ftCount.add(len + 1, 1);57        ftSum.add(len + 1, len);58    }59 60    private void removeSegment(int len) {61        if (len <= 0) return;62        ftCount.add(len + 1, -1);63        ftSum.add(len + 1, -len);64    }65 66    private long countGroups(int k) {67        if (k > n) return 0;68        if (breaks.isEmpty()) return n;69        int kPrime = k - 1;70        long totalSumL = ftSum.query(n + 1) - ftSum.query(kPrime);71        long totalCount = ftCount.query(n + 1) - ftCount.query(kPrime);72        return totalSumL - (long) (k - 2) * totalCount;73    }74 75    private void updateColor(int index, int newColor) {76        if (colors[index] == newColor) return;77        colors[index] = newColor;78        updateGood((index - 1 + n) % n);79        updateGood(index);80    }81 82    private void updateGood(int p) {83        boolean newGood = (colors[p] != colors[(p + 1) % n]);84        if (good[p] == newGood) return;85        good[p] = newGood;86 87        if (newGood) { // 0 -> 1: removing a break88            Integer bPrev = breaks.lower(p); if (bPrev == null) bPrev = breaks.last();89            Integer bNext = breaks.higher(p); if (bNext == null) bNext = breaks.first();90            breaks.remove(p);91            removeSegment(getLength(bPrev, p));92            removeSegment(getLength(p, bNext));93            if (breaks.isEmpty()) return; // All good now, handled by countGroups94            addSegment(getLength(bPrev, bNext));95        } else { // 1 -> 0: adding a break96            if (breaks.isEmpty()) { // Was all good97                breaks.add(p);98                addSegment(n - 1);99                return;100            }101            Integer bPrev = breaks.lower(p); if (bPrev == null) bPrev = breaks.last();102            Integer bNext = breaks.higher(p); if (bNext == null) bNext = breaks.first();103            removeSegment(getLength(bPrev, bNext));104            addSegment(getLength(bPrev, p));105            addSegment(getLength(p, bNext));106            breaks.add(p);107        }108    }109}

Complexity

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.

Trade-offs

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.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem