Alternating Groups III - Practice Coding Problems

Alternating Groups III - Problem

There are some red and blue tiles arranged in a circle. You are given an array of integers colors and a 2D array of integers queries.

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 a contiguous subset of tiles in the circle with alternating colors (each tile in the group except the first and last one has a different color from its adjacent tiles in the group).

You have to process queries of two types:

queries[i] = [1, size_i]: determine the count of alternating groups with size size_i
queries[i] = [2, index_i, color_i]: change colors[index_i] to color_i

Return an array answer containing the results of the queries of the first type in order.

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 Pattern Counting

$ Input: colors = [0,1,1,0,1], queries = [[1,3],[2,1,0],[1,3]]

› Output: [2,2]

💡 Note: First query [1,3] counts alternating groups of size 3. Groups [1,0,1] at positions (2,3,4) and (3,4,0) are valid. After updating index 1 to 0, we still have 2 groups of size 3.

Example 2 — Size 1 Groups

$ Input: colors = [0,0,1,0], queries = [[1,4],[2,0,1],[1,4]]

› Output: [1,0]

💡 Note: Initially only one alternating group of size 4 exists. After changing colors[0] to 1, no alternating groups of size 4 remain.

Example 3 — All Same Colors

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

› Output: [0]

💡 Note: No alternating groups of size 2 exist when all colors are the same.

Constraints

1 ≤ colors.length ≤ 5 × 10⁴
0 ≤ colors[i] ≤ 1
1 ≤ queries.length ≤ 5 × 10⁴
queries[i][0] ∈ {1, 2}
For type 1 queries: 1 ≤ size_i ≤ colors.length
For type 2 queries: 0 ≤ index_i < colors.length, 0 ≤ color_i ≤ 1

Visualization

Tap to expand

Understanding the Visualization

Input

Circular array of colors [0,1,1,0,1] and queries

Pattern Detection

Find alternating groups of specified sizes

Dynamic Updates

Handle color changes and recount patterns

Key Takeaway

🎯 Key Insight: Efficiently track alternating segments in circular arrays and update only affected regions on color changes

Asked in

G Google 15 f Meta 12 a Amazon 8

The key insight is to efficiently track alternating color patterns in a circular array while handling dynamic updates. The optimal approach uses segment tracking to pre-compute alternating lengths and update only affected regions. Time: O(Q × N), Space: O(N)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(Q × N × S)	O(1)	For each query, scan the entire circle to count alternating groups of the required size
Segment Tracking	O(Q × N)	O(N)	Track alternating segments and update only affected regions when colors change

Brute Force — Algorithm Steps

Process each query sequentially
For count queries: check all positions for alternating patterns of given size
For update queries: change the color at specified index

Visualization

Tap to expand

Step-by-Step Walkthrough

Query Processing

Process each query sequentially

Pattern Checking

For count queries, check all positions

Color Updates

For update queries, change color directly

Code -

solution.c — C

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

int countAlternatingGroups(int* colors, int n, int size) {
    if (size == 1) return n;
    if (size > n) return 0;
    
    int count = 0;
    for (int start = 0; start < n; start++) {
        int isAlternating = 1;
        for (int i = 1; i < size; i++) {
            int pos = (start + i) % n;
            int prevPos = (start + i - 1) % n;
            if (colors[pos] == colors[prevPos]) {
                isAlternating = 0;
                break;
            }
        }
        if (isAlternating) count++;
    }
    return count;
}

int* solution(int* colors, int colorsSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
    int* result = (int*)malloc(queriesSize * sizeof(int));
    int resultIndex = 0;
    
    int* colorsCopy = (int*)malloc(colorsSize * sizeof(int));
    for (int i = 0; i < colorsSize; i++) {
        colorsCopy[i] = colors[i];
    }
    
    for (int i = 0; i < queriesSize; i++) {
        if (queries[i][0] == 1) {
            result[resultIndex++] = countAlternatingGroups(colorsCopy, colorsSize, queries[i][1]);
        } else {
            colorsCopy[queries[i][1]] = queries[i][2];
        }
    }
    
    *returnSize = resultIndex;
    free(colorsCopy);
    return result;
}

int main() {
    // Simplified example
    int colors[] = {0, 1, 1, 0, 1};
    int* queries[3];
    int query1[] = {1, 3};
    int query2[] = {2, 1, 0};
    int query3[] = {1, 3};
    queries[0] = query1;
    queries[1] = query2;
    queries[2] = query3;
    int queriesColSize[] = {2, 3, 2};
    
    int returnSize;
    int* result = solution(colors, 5, queries, 3, queriesColSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(Q × N × S)

Q queries, each count query checks N positions with up to S comparisons

✓ Linear Growth

Space Complexity

O(1)

Only using variables for iteration, no extra data structures

✓ Linear Space

3.2K Views

Medium Frequency

~35 min Avg. Time

145 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

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler