Alternating Groups I

Difficulty: Easy | Acceptance: 69.00% | Paid: No Topics: Array, Sliding Window

There is a circle of n colors. You are given an array colors of size n where colors[i] represents the color of the ith color in the circle.

An alternating group is a group of 3 consecutive colors in the circle such that:

The first and third colors are the same. The first and third colors are different from the second color. More formally, a group of 3 colors colors[i], colors[j], colors[k] is an alternating group if:

i < j < k colors[i] == colors[k] colors[i] != colors[j] Return the number of alternating groups in the circle.

• Examples
• Constraints
• Approach 1: Iteration with Modulo
• Approach 2: Array Concatenation

Examples

Example 1

Input:

colors = [1,1,1]

Output:

0

Example 2

Input:

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

Output:

3

Explanation: Alternating groups:

Constraints

- 3 <= colors.length <= 100
- 0 <= colors[i] <= 1

Approach 1: Iteration with Modulo

Intuition Since the colors are arranged in a circle, we can iterate through the array and treat each index as the start of a potential group of three. We use the modulo operator to handle the wrap-around from the end of the array back to the beginning.

Steps

• Initialize a counter to 0.
• Iterate through the array from index 0 to n-1.
• For each index i, identify the three colors of the group: colors[i], colors[(i+1)%n], and colors[(i+2)%n].
• Check if the first and third colors are the same and different from the second color.
• If the condition is met, increment the counter.
• Return the counter.

from typing import List

class Solution:
    def numberOfAlternatingGroups(self, colors: List[int]) -> int:
        n = len(colors)
        count = 0
        for i in range(n):
            first = colors[i]
            second = colors[(i + 1) % n]
            third = colors[(i + 2) % n]
            if first == third and first != second:
                count += 1
        return count

Complexity

• Time: O(n)
• Space: O(1)
• Notes: This is the most space-efficient approach as it only requires a few variables for iteration and comparison.

Approach 2: Array Concatenation

Intuition To avoid the complexity of modulo arithmetic, we can conceptually “unroll” the circle by concatenating the array with itself. This allows us to check groups of three linearly from index 0 to n-1 without worrying about wrapping around the array bounds.

Steps

• Create a new array extended by appending the original colors array to itself.
• Iterate through the first n elements of the extended array.
• For each index i, check the triplet extended[i], extended[i+1], and extended[i+2].
• If the first and third elements are equal and different from the second, increment the counter.
• Return the counter.

from typing import List

class Solution:
    def numberOfAlternatingGroups(self, colors: List[int]) -> int:
        n = len(colors)
        extended = colors + colors
        count = 0
        for i in range(n):
            if extended[i] == extended[i + 2] and extended[i] != extended[i + 1]:
                count += 1
        return count

Complexity

• Time: O(n)
• Space: O(n)
• Notes: This approach trades space for simplicity in logic, avoiding the modulo operator.