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 tilei
is red.colors[i] == 1
means that tilei
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.
Examples
Example 1:
|
|
Example 2:
|
|
Alternating groups:
Constraints:
3 <= colors.length <= 100
0 <= colors[i] <= 1
Solution
Method 1 – Sliding Window with Modulo
Intuition
Since the tiles form a circle, we can use a sliding window of size 3 and wrap around using modulo. For each window, we check if the middle tile is different from both its neighbors. This way, we count all valid alternating groups efficiently.
Approach
- Let
n
be the length ofcolors
. - Initialize
ans
to 0. - For each index
i
from 0 ton-1
:
- Let
a = colors[i]
- Let
b = colors[(i+1)%n]
- Let
c = colors[(i+2)%n]
- If
b
is different from botha
andc
, incrementans
.
- Return
ans
.
Code
|
|
|
|
|
|
Complexity
- ⏰ Time complexity:
O(N)
— We check each possible group once. - 🧺 Space complexity:
O(1)
— Only a few variables are used.