Alternating Groups I - Practice Coding Problems

Alternating Groups I - 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 tile i is red
colors[i] == 1 means that tile i 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: Since colors represents a circle, the first and the last tiles are considered to be next to each other.

Input & Output

Example 1 — Basic Circle

$ Input: colors = [0,1,0,0,1]

› Output: 2

💡 Note: Position 1: colors[0,1,2] = [0,1,0] - middle 1 differs from both 0s ✓. Position 4: colors[3,4,0] = [0,1,0] - middle 1 differs from both 0s ✓. Total: 2 groups.

Example 2 — No Alternating

$ Input: colors = [0,1,1,0,1]

› Output: 1

💡 Note: Only position 3 forms alternating group: colors[2,3,4] = [1,0,1] - middle 0 differs from both 1s ✓. Other positions don't form alternating patterns.

Example 3 — All Same Color

$ Input: colors = [1,1,1]

› Output: 0

💡 Note: All tiles are same color (blue), so no middle tile can differ from its neighbors. No alternating groups possible.

Constraints

3 ≤ colors.length ≤ 100
0 ≤ colors[i] ≤ 1

Visualization

Tap to expand

Understanding the Visualization

Input

Circular array of 0s and 1s representing tile colors

Process

Find groups where middle tile differs from neighbors

Output

Count of alternating groups found

Key Takeaway

🎯 Key Insight: Use modular arithmetic to handle circular array wraparound when checking neighbors

Asked in

f Meta 15 G Google 12

The key insight is to check each position as the middle of a potential alternating group using modular arithmetic for circular array access. Best approach is single pass checking each position. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window	O(n)	O(1)	Use sliding window of size 3 to check alternating patterns
Single Pass Check	O(n)	O(1)	Check each position as middle of alternating group

Sliding Window — Algorithm Steps

Create sliding window of size 3
Check alternating pattern in current window
Slide window and repeat for all positions

Visualization

Tap to expand

Step-by-Step Walkthrough

Position Window

Place 3-element window at current position

Check Pattern

Verify middle differs from both ends

Slide Window

Move window to next position

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* colors, int n) {
    if (n < 3) return 0;
    
    int count = 0;
    for (int i = 0; i < n; i++) {
        // Window: [i-1, i, i+1] with wraparound
        int prev = colors[(i - 1 + n) % n];
        int curr = colors[i];
        int next = colors[(i + 1) % n];
        
        // Check if current position forms alternating group
        if (curr != prev && curr != next) {
            count++;
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array
    int colors[1000];
    int n = 0;
    char* ptr = strchr(line, '[');
    if (ptr) {
        ptr++;
        char* token = strtok(ptr, ",]");
        while (token) {
            colors[n++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    int result = solution(colors, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through all positions with constant work per position

✓ Linear Growth

Space Complexity

O(1)

Only storing window indices and counters

✓ Linear Space

12.5K Views

Medium Frequency

~15 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sliding Window — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler