Alternating Groups II - Practice Coding Problems

Alternating Groups II - Problem

There is a circle of red and blue tiles. You are given an array of integers colors and an integer k.

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

An alternating group is every k contiguous tiles in the circle with alternating colors (each tile in the group except the first and last one has a different color from its left and right tiles).

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.

Input & Output

Example 1 — Basic Alternating Pattern

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

› Output: 3

💡 Note: The alternating groups are: [0,1,0] starting at index 0, [1,0,1] starting at index 1, and [0,1,0] starting at index 2. Since it's circular, indices wrap around.

Example 2 — Partial Alternating

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

› Output: 0

💡 Note: No group of 4 consecutive tiles alternates. For example, [0,1,0,0] has two consecutive 0s, so it doesn't alternate.

Example 3 — All Same Color

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

› Output: 0

💡 Note: All tiles are the same color, so no alternating groups of any size exist.

Constraints

3 ≤ colors.length ≤ 10⁵
1 ≤ k ≤ colors.length
colors[i] is either 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input

Circular array of red (0) and blue (1) tiles, target group size k

Process

Find all k consecutive tiles that alternate in color

Output

Count of valid alternating groups

Key Takeaway

🎯 Key Insight: Track alternating segment lengths and calculate how many k-groups each segment can form

Asked in

G Google 25 M Microsoft 20 a Amazon 15

The key insight is to use a sliding window approach to track alternating segments efficiently. Instead of checking each position independently, we maintain the length of current alternating sequences. When a sequence of length L alternates, it can form max(0, L-k+1) groups of size k. Best approach is sliding window with Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window - Track Alternating Segments	O(n)	O(n)	Track the length of current alternating sequence and calculate valid groups efficiently
Brute Force - Check Every Position	O(n×k)	O(1)	For each starting position, check if the next k tiles form an alternating pattern

Sliding Window - Track Alternating Segments — Algorithm Steps

Extend array to handle circular nature
Track current alternating sequence length
When sequence breaks, calculate groups from previous segment
Sum up all valid groups

Visualization

Tap to expand

Step-by-Step Walkthrough

Track Sequence

Maintain running count of alternating tiles

Calculate Groups

When sequence breaks, calculate how many k-groups it contains

Sum Results

Add up groups from all alternating segments

Code -

solution.c — C

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

int solution(int* colors, int n, int k) {
    if (k == 1) {
        return n;
    }
    
    // Extend array to handle circular nature
    int* extended = malloc(2 * n * sizeof(int));
    for (int i = 0; i < n; i++) {
        extended[i] = colors[i];
        extended[i + n] = colors[i];
    }
    
    int count = 0;
    int currentLength = 1;  // Length of current alternating sequence
    
    for (int i = 1; i < 2 * n; i++) {
        if (extended[i] != extended[i-1]) {
            currentLength++;
        } else {
            // Calculate groups from previous alternating segment
            if (currentLength >= k) {
                // Ensure we don't double count in circular extension
                int validLength = currentLength < n + k - 1 ? currentLength : n + k - 1;
                int groups = validLength - k + 1;
                if (groups > 0) {
                    count += groups;
                }
            }
            currentLength = 1;
        }
        
        // Stop when we've processed enough for circular
        if (i >= n + k - 1) {
            break;
        }
    }
    
    // Handle final segment
    if (currentLength >= k) {
        int validLength = currentLength < n + k - 1 ? currentLength : n + k - 1;
        int groups = validLength - k + 1;
        if (groups > 0) {
            count += groups;
        }
    }
    
    free(extended);
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int colors[1000];
    int n = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        colors[n++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(colors, n, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the extended array to track alternating segments

✓ Linear Growth

Space Complexity

O(n)

Creating extended array to handle circular nature

⚡ Linearithmic Space

32.0K Views

Medium Frequency

~25 min Avg. Time

850 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 - Track Alternating Segments — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler