LeetCode Problem 3206

Difficulty: 🟢 Easy
Topics: Array, Sliding Window

Solution

Problem Understanding

The problem gives us a circular array called colors, where each element represents the color of a tile:

• 0 means red
• 1 means blue

Because the tiles form a circle, the first and last tiles are considered adjacent.

We need to count how many groups of exactly 3 contiguous tiles form an alternating group. A group is considered alternating when the middle tile is different from both of its neighbors.

For any three consecutive tiles:

[a, b, c]

the group is alternating if:

a != b and b != c

Since the colors are only 0 and 1, this automatically means:

a == c and a != b

The circular nature is very important. When checking groups near the end of the array, we wrap around to the beginning. For example, if n = len(colors), then:

• the neighbor after index n - 1 is index 0
• the neighbor before index 0 is index n - 1

The constraints are very small:

3 <= colors.length <= 100

This tells us that even an inefficient solution would still run comfortably within limits. However, the goal is to understand the cleanest and most efficient way to solve the problem.

Several edge cases are important:

• All tiles have the same color, so no alternating groups exist.
• Alternation may occur across the circular boundary.
• Arrays of minimum size 3 must still correctly handle wraparound logic.
• Consecutive alternating patterns such as [0,1,0,1,0] produce many valid groups.

A naive implementation can easily make mistakes when handling circular indexing, especially for groups that include the first and last elements together. The problem describes a circular arrangement of tiles, where each tile is either red (0) or blue (1). Because the tiles form a circle, the first and last elements are considered adjacent.

We are asked to count how many groups of three consecutive tiles form an “alternating group.” A group of three tiles (i-1, i, i+1) is considered alternating if the middle tile has a different color from both its left and right neighbors. In other words, the condition is:

• colors[i] != colors[i-1]
• colors[i] != colors[i+1]

Since the array is circular, indices wrap around, so index -1 corresponds to n-1, and index n corresponds to 0.

The input size is small, with 3 <= n <= 100, which indicates that even straightforward linear or quadratic approaches will be efficient enough. However, the structure suggests we should aim for a simple linear scan.

Edge Cases to Consider

The most important edge cases involve uniform arrays where all tiles are the same color, arrays where colors alternate perfectly, and minimal length arrays of size 3 where wrap-around is essential. These cases help ensure correct handling of circular indexing and correct identification of valid triples.

Approaches

Brute Force Approach

The brute force solution checks every possible group of 3 consecutive tiles.

For each index i, we examine:

colors[i]
colors[(i + 1) % n]
colors[(i + 2) % n]

The modulo operation allows the indices to wrap around the circle.

We then verify whether the middle tile differs from both neighbors:

colors[i] != colors[(i + 1) % n]
and
colors[(i + 1) % n] != colors[(i + 2) % n]

If both conditions hold, we increment the answer.

This approach is completely correct because every possible contiguous group of length 3 is checked exactly once.

Although this method is technically brute force, it is already optimal for this problem because each tile must be inspected at least once.

Key Insight

The important observation is that a valid alternating group only depends on three adjacent tiles.

There is no need for complicated data structures, sliding window maintenance, or preprocessing. Since the window size is fixed at exactly 3, we can directly test every group in constant time.

The circular structure is handled naturally with modulo indexing.

This gives a very clean linear-time solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Checks every group of 3 directly
Optimal	O(n)	O(1)	Same idea, minimal and efficient implementation

Algorithm Walkthrough

1. Store the length of the array in n.

We need this value repeatedly for circular indexing. 2. Initialize a counter variable answer = 0.

This variable tracks how many alternating groups we find. 3. Iterate through every index i from 0 to n - 1.

Each index represents the starting position of a group of 3 contiguous tiles. 4. Compute the three indices in the group.

The tiles are:

first  = colors[i]
second = colors[(i + 1) % n]
third  = colors[(i + 2) % n]

The modulo operator % n ensures that indices wrap around correctly for the circular array. 5. Check whether the group alternates.

The condition is:

first != second and second != third

If true, increment answer. 6. After processing all positions, return answer.

Why it works

Every contiguous group of length 3 in the circle has exactly one starting index. The algorithm iterates through all possible starting indices and checks the exact condition required for alternation.

Because modulo indexing correctly models the circular structure, groups that cross the boundary between the end and beginning of the array are also handled correctly.

Therefore, every valid group is counted exactly once. The brute force idea is to explicitly check every index as the center of a triple. For each index i, we compute its left and right neighbors using modular arithmetic and verify whether the middle tile differs from both neighbors.

This approach is correct because it directly evaluates every possible group of three consecutive tiles in the circular structure. However, it is essentially the same as the optimal solution in terms of work, since each index is checked independently with constant time operations.

Key Insight

The key observation is that each valid alternating group is uniquely determined by its center index. There is no need for nested loops or sliding window state maintenance beyond simple index arithmetic. Each position contributes independently to the final count.

Thus, the problem reduces to a single pass over the array with modular indexing.

Complexity Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Check each index as center of a triple using modular arithmetic
Optimal	O(n)	O(1)	Single pass, same checks but framed directly as linear scan

Algorithm Walkthrough

We compute the result by iterating through every index and treating it as the middle of a triple.

1. Initialize a counter count = 0. This will store the number of valid alternating groups found in the circular array.
2. Iterate over every index i from 0 to n - 1. Each index represents the middle tile of a potential group of three.
3. For each index i, compute the left neighbor index as (i - 1 + n) % n and the right neighbor index as (i + 1) % n. This ensures correct circular behavior.
4. Check whether colors[i] is different from both colors[left] and colors[right]. If both conditions hold, increment count by 1.
5. After processing all indices, return count as the final result.

Why it works

Each valid alternating group is uniquely identified by its center tile. Because every group of three consecutive tiles has exactly one center index, iterating through all indices guarantees that every possible group is evaluated exactly once. Circular indexing ensures that wrap-around groups are correctly included.

Python Solution

from typing import List

class Solution:
    def numberOfAlternatingGroups(self, colors: List[int]) -> int:
        n = len(colors)
        alternating_groups = 0

        for i in range(n):
            first = colors[i]
            second = colors[(i + 1) % n]
            third = colors[(i + 2) % n]

            if first != second and second != third:
                alternating_groups += 1

        return alternating_groups

The implementation begins by storing the array length in n. This makes the modulo operations simpler and avoids repeated calls to len(colors).

The variable alternating_groups stores the running count of valid groups.

The loop iterates through every index in the circular array. For each position, the next two elements are accessed using modulo arithmetic:

(i + 1) % n
(i + 2) % n

This is the key step that converts normal array traversal into circular traversal.

The condition:

first != second and second != third

directly matches the definition of an alternating group. Whenever the condition is true, the counter increases.

Finally, the function returns the total count. count = 0

    for i in range(n):
        left = (i - 1 + n) % n
        right = (i + 1) % n

        if colors[i] != colors[left] and colors[i] != colors[right]:
            count += 1

    return count

### Explanation of Implementation

The solution first stores the length of the array to avoid recomputation. It then iterates through each index, treating it as the center of a possible alternating group. The left and right neighbors are computed using modular arithmetic to ensure circular behavior.

The condition directly checks whether the center differs from both neighbors. If it does, the counter is incremented. Finally, the accumulated count is returned.

## Go Solution

```go
func numberOfAlternatingGroups(colors []int) int {
	n := len(colors)
	alternatingGroups := 0

	for i := 0; i < n; i++ {
		first := colors[i]
		second := colors[(i+1)%n]
		third := colors[(i+2)%n]

		if first != second && second != third {
			alternatingGroups++
		}
	}

	return alternatingGroups
}

The Go implementation follows exactly the same logic as the Python version.

Slices in Go already behave similarly to dynamic arrays, so no additional handling is required. Since the constraints are very small, integer overflow is not a concern.

Modulo indexing works identically and handles the circular traversal cleanly. n := len(colors) count := 0

for i := 0; i < n; i++ {
    left := (i - 1 + n) % n
    right := (i + 1) % n

    if colors[i] != colors[left] && colors[i] != colors[right] {
        count++
    }
}

return count

}

### Go-specific Notes

The Go implementation mirrors the Python logic closely. Slice indexing behaves the same, but we must explicitly handle modular arithmetic for circular indexing. There are no concerns with overflow due to the small constraints. Unlike Python, Go requires explicit variable declarations, but otherwise the logic is identical.

## Worked Examples

### Example 1

colors = [1,1,1]

Here:

n = 3

We examine every starting index.

| i | Group | Alternating? | Count |
| --- | --- | --- | --- |
| 0 | [1,1,1] | No | 0 |
| 1 | [1,1,1] | No | 0 |
| 2 | [1,1,1] | No | 0 |

Final answer:

0

No middle tile differs from both neighbors.

### Example 2

colors = [0,1,0,0,1]

Here:

n = 5

We process every possible group.

| i | Group | Alternating? | Count |
| --- | --- | --- | --- |
| 0 | [0,1,0] | Yes | 1 |
| 1 | [1,0,0] | No | 1 |
| 2 | [0,0,1] | No | 1 |
| 3 | [0,1,0] | Yes | 2 |
| 4 | [1,0,1] | Yes | 3 |

Final answer:

3

Notice that the final group wraps around the array:

[colors[4], colors[0], colors[1]]

[1,0,1]

This demonstrates why modulo indexing is necessary.
Input: `[1, 1, 1]`

We evaluate each index:

| i | left | right | colors[i] | colors[left] | colors[right] | Valid |
| --- | --- | --- | --- | --- | --- | --- |
| 0 | 2 | 1 | 1 | 1 | 1 | No |
| 1 | 0 | 2 | 1 | 1 | 1 | No |
| 2 | 1 | 0 | 1 | 1 | 1 | No |

Final result: `0`

No index satisfies the condition because all values are identical.

### Example 2

Input: `[0, 1, 0, 0, 1]`

We check each index:

| i | left | right | triple | valid |
| --- | --- | --- | --- | --- |
| 0 | 4 | 1 | (1,0,1) | yes |
| 1 | 0 | 2 | (0,1,0) | yes |
| 2 | 1 | 3 | (1,0,0) | no |
| 3 | 2 | 4 | (0,0,1) | no |
| 4 | 3 | 0 | (0,1,0) | yes |

Final result: `3`

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(n) | Each index is processed exactly once |
| Space | O(1) | Only a few variables are used |

The algorithm performs a constant amount of work for each tile in the array. Since there are `n` tiles, the total running time is linear.

No additional data structures proportional to the input size are allocated, so the extra space usage remains constant.

## Test Cases

```python
from typing import List

class Solution:
    def numberOfAlternatingGroups(self, colors: List[int]) -> int:
        n = len(colors)
        answer = 0

        for i in range(n):
            if (
                colors[i] != colors[(i + 1) % n]
                and colors[(i + 1) % n] != colors[(i + 2) % n]
            ):
                answer += 1

        return answer

solution = Solution()

assert solution.numberOfAlternatingGroups([1, 1, 1]) == 0  # all same color
assert solution.numberOfAlternatingGroups([0, 1, 0, 0, 1]) == 3  # provided example
assert solution.numberOfAlternatingGroups([0, 1, 0]) == 3  # every group alternates
assert solution.numberOfAlternatingGroups([0, 0, 0]) == 0  # minimum size, no alternation
assert solution.numberOfAlternatingGroups([1, 0, 1, 0]) == 4  # fully alternating circle
assert solution.numberOfAlternatingGroups([0, 1, 1, 0]) == 0  # no valid middle tile
assert solution.numberOfAlternatingGroups([0, 1, 0, 1, 0]) == 5  # all windows alternate
assert solution.numberOfAlternatingGroups([1, 0, 0, 1, 0]) == 3  # mixed pattern
assert solution.numberOfAlternatingGroups([0, 0, 1, 0, 0]) == 1  # single valid group

Test	Why
[1,1,1]	Verifies no alternating groups exist
[0,1,0,0,1]	Validates the provided example
[0,1,0]	Tests minimum size where every group alternates
[0,0,0]	Tests minimum size with no alternation
[1,0,1,0]	Verifies fully alternating circular pattern
[0,1,1,0]	Ensures adjacent equal values invalidate groups
[0,1,0,1,0]	Tests many consecutive alternating windows
[1,0,0,1,0]	Tests mixed valid and invalid groups
[0,0,1,0,0]	Tests exactly one valid group

Edge Cases

One important edge case is when all tiles have the same color, such as:

[1,1,1]

A buggy implementation might incorrectly count some groups because the circle wraps around. However, the condition:

first != second and second != third

correctly rejects every group because adjacent tiles are equal everywhere.

Another important edge case is the minimum allowed array size:

n = 3

Since the structure is circular, the algorithm still examines exactly three groups, one starting at each index. Modulo indexing ensures that wraparound access works safely without going out of bounds.

A third important case is a fully alternating circle:

[0,1,0,1]

In this situation, every possible group of length 3 is valid. Some implementations accidentally skip groups that cross the boundary between the end and beginning of the array. Using modulo indexing guarantees that those groups are included correctly.

A fourth subtle case occurs when only some windows alternate, such as:

[0,1,1,0,1]

The implementation checks each window independently, so overlapping valid and invalid groups are handled naturally without interference between iterations. | Time | O(n) | Each index is visited once and constant time checks are performed | | Space | O(1) | Only a few variables are used regardless of input size |

The solution is linear because we perform exactly one pass through the array, and all operations inside the loop are constant time.

Test Cases

# provided examples
assert Solution().numberOfAlternatingGroups([1, 1, 1]) == 0  # all same color
assert Solution().numberOfAlternatingGroups([0, 1, 0, 0, 1]) == 3  # example case

# minimal circular case
assert Solution().numberOfAlternatingGroups([0, 1, 0]) == 3  # all centers valid in alternating cycle

# no alternating groups
assert Solution().numberOfAlternatingGroups([0, 0, 0, 0]) == 0  # uniform array

# alternating pattern
assert Solution().numberOfAlternatingGroups