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 tilei
is red.colors[i] == 1
means that tilei
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 sizesizei
.queries[i] = [2, indexi, colori]
, changecolors[indexi]
tocolori
.
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.
Examples
Example 1:
|
|
**
First query:
Change colors[1]
to 0.
Second query: Count of the alternating groups with size 4:
Example 2:
|
|
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^4
0 <= colors[i] <= 1
1 <= queries.length <= 5 * 104
queries[i][0] == 1
orqueries[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
Solution
Method 1 – Sliding Window with Circular Handling
Intuition
The key idea is to use a sliding window of the required size to check for alternating groups efficiently. Since the array is circular, we need to handle wrap-around cases. For updates, we simply change the color and process queries as needed.
Approach
- Sliding Window for Alternating Groups:
- For a query
[1, size]
, slide a window of lengthsize
over the array. - For each window, check if the colors alternate (i.e., adjacent tiles have different colors).
- Since the array is circular, extend the array by concatenating the first
size-1
elements to the end for wrap-around. - Count all valid windows.
- Processing Updates:
- For a query
[2, idx, color]
, updatecolors[idx]
tocolor
.
- Handling Queries:
- Iterate through queries, process each according to its type, and collect answers for type 1 queries.
- Edge Cases:
- Ensure window does not double-count groups due to circularity.
- Only consider windows starting within the original array length.
Code
|
|
|
|
|
|
Complexity
- ⏰ Time complexity:
O(Q * N * S)
whereQ
is the number of queries,N
is the length of colors, andS
is the group size (worst case up toN
). - 🧺 Space complexity:
O(N)
for the extended array per query.