Watch 3 video solutions for Alternating Groups III, a hard level problem involving Array, Binary Indexed Tree. This walkthrough by codingMohan has 1,821 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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 * 1040 <= colors[i] <= 11 <= queries.length <= 5 * 104queries[i][0] == 1 or queries[i][0] == 2i that:
queries[i][0] == 1: queries[i].length == 2, 3 <= queries[i][1] <= colors.length - 1queries[i][0] == 2: queries[i].length == 3, 0 <= queries[i][1] <= colors.length - 1, 0 <= queries[i][2] <= 1Problem Overview: You are given a circular array of colors and a sequence of queries. Some queries update the color at an index, while others ask how many alternating groups of a given size exist in the array. An alternating group means adjacent elements strictly alternate (e.g., 0,1,0,1). Because updates modify the structure dynamically, the solution must efficiently maintain alternating segments while answering queries quickly.
Approach 1: Recursive Approach with Memoization (Brute-Force Simulation) (Time: O(n * q), Space: O(n))
The most direct method recomputes alternating segments whenever a query asks for the number of valid groups. Traverse the array and recursively check whether consecutive elements alternate, storing intermediate results with memoization to avoid recomputing overlapping segments. For each query, scan the array and count segments whose length satisfies the requested size. This works for small inputs but becomes slow when updates and queries are frequent because each query may require scanning most of the array.
Approach 2: Dynamic Programming with Binary Indexed Tree (Optimal) (Time: O((n + q) log n), Space: O(n))
The efficient strategy tracks maximal alternating segments instead of recomputing them from scratch. First, determine whether each adjacent pair alternates. This transforms the problem into maintaining runs of valid alternating edges. When a color update occurs, only the two neighboring relationships change, so the affected segments can be split or merged locally. Use a Binary Indexed Tree to store counts of segment lengths and support prefix queries for "how many segments have length ≥ k".
Dynamic programming ideas help maintain the length of alternating runs starting at each index. When an update breaks or forms alternation, adjust the boundaries of the affected segments and update their lengths in the Fenwick tree. Each modification touches only a constant number of segments, keeping updates efficient. Query operations then become simple range queries over segment lengths using the BIT.
This approach works well because it converts a structural property of the array into a frequency problem that a Fenwick tree handles efficiently. The array itself is still accessed directly for updates, while the BIT maintains aggregate statistics about segment sizes.
Recommended for interviews: The Binary Indexed Tree solution is what interviewers expect for a hard problem with dynamic updates. The brute-force or recursive simulation demonstrates you understand how alternating groups are formed, but the optimized structure shows you can maintain derived properties under updates. Strong candidates recognize that only local relationships change after an update and use data structures like a array plus Fenwick tree or segment tree to maintain counts efficiently. Concepts from dynamic programming help track alternating run lengths, while the BIT enables fast aggregated queries.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Simulation with Memoization | O(n * q) | O(n) | Good for understanding how alternating groups form; feasible only when constraints are small |
| Dynamic Programming + Binary Indexed Tree | O((n + q) log n) | O(n) | Best for large inputs with frequent updates and queries; maintains segment counts efficiently |