3208. Alternating Groups II Solution

Q: Is Alternating Groups II easy or hard?

Alternating Groups II is rated Medium. The main challenge is handling the circular array and recognizing that a group of k elements depends on k-1 alternating neighbor comparisons. Once that insight is clear, a linear-time sliding window solution becomes straightforward.

Q: Alternating Groups II Python/Java solution

Most implementations iterate through the circular array and maintain a sliding window that tracks alternating edges. The logic is identical across Python, Java, C++, and other languages: update the window state as you move forward and increment the count whenever k tiles satisfy the alternating condition.

Q: How to solve Alternating Groups II in O(n)?

Track whether adjacent tiles alternate and maintain a sliding window representing k consecutive tiles. A group is valid when the window contains exactly k-1 alternating edges. Update the window as you move forward across the circular array using modulo indexing to handle wrap-around.

Q: What is the best approach for Alternating Groups II?

The best approach uses a sliding window to track whether each group of k tiles maintains alternating neighbors. A valid group requires k-1 alternating edges. By updating the window incrementally while traversing the circular array, you count valid groups in O(n) time with O(1) extra space.

Q: Is Alternating Groups II asked at Google/Amazon/Meta?

Alternating pattern and sliding window problems frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the technique of counting valid windows based on adjacency conditions is a common interview pattern.

Q: What data structure is used in Alternating Groups II?

The core data structure is an array combined with a sliding window technique. Some implementations also use an auxiliary array to store whether adjacent elements alternate, which simplifies pattern detection before applying the window.

Q: What is the time complexity of Alternating Groups II?

The optimal solution runs in O(n) time where n is the number of tiles in the colors array. Each element is processed a constant number of times while maintaining the sliding window. Space complexity can be O(1) with direct window tracking or O(n) if an auxiliary array is used.

The 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.

Example 1:

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

Output: 3

Explanation:

Alternating groups:

Example 2:

Input: colors = [0,1,0,0,1,0,1], k = 6

Output: 2

Explanation:

Alternating groups:

Example 3:

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

Output: 0

Explanation:

Constraints:

3 <= colors.length <= 10⁵
0 <= colors[i] <= 1
3 <= k <= colors.length

Approach overview

Problem Overview: You are given a circular array colors and an integer k. A group is valid if the k consecutive tiles form an alternating pattern, meaning every adjacent pair has different colors. Because the array is circular, groups may wrap from the end back to the start.

Approach 1: Sliding Window on Alternation Count (O(n) time, O(1) space)

This approach treats the problem as checking whether each window of size k maintains alternating neighbors. For a group of length k, there must be exactly k-1 alternating edges. Iterate through the array while maintaining a sliding window that tracks whether adjacent elements differ. Since the array is circular, iterate up to n + k positions or use modulo indexing. Each step updates the number of valid alternating edges in the current window; when the count reaches k-1, you found a valid group. This technique is common in sliding window problems where the window property can be updated incrementally instead of recomputed.

Approach 2: Pattern Recognition with Auxiliary Array (O(n) time, O(n) space)

Another way to think about the problem is to precompute whether each adjacent pair alternates. Build an auxiliary array alt where alt[i] = 1 if colors[i] != colors[(i+1) % n], otherwise 0. A valid group of size k requires k-1 consecutive ones in this array. After building the array, run a sliding window of size k-1 across the circular structure and count windows whose sum equals k-1. This separates pattern detection from counting, which makes the logic easier to reason about when working with array transformations and pattern scanning.

The key insight across both solutions is that alternating groups are defined by edges between elements, not the elements themselves. Once you track whether neighboring values differ, the problem reduces to counting stretches of valid edges. The circular nature only affects indexing, which you handle using modulo operations or by extending the traversal range.

Recommended for interviews: The sliding window approach is the expected solution. It runs in O(n) time with constant extra space and demonstrates strong understanding of window maintenance and circular traversal. The auxiliary-array method is also linear time but uses extra memory; it’s easier to reason about and can help you derive the optimal solution during an interview.

Approach 1: Sliding Window Approach

In this approach, we utilize a sliding window to evaluate each possible group of k contiguous tiles within the circle. Since the array represents a circle, special attention is required to wrap around the end of the array. The key is to check each time whether the subarray of size k has alternating colors. As we slide the window, we determine if a new k-sized subarray maintains an alternating pattern; if so, we increment our count of alternating groups.

Python

def count_alternating_groups(colors, k):
    n = len(colors)
    count = 0
    for i in range(n):
        valid = True
        for j in range(1, k):
            if colors[(i + j) % n] == colors[(i + j - 1) % n]:
                valid = False
                break
        if valid:
            count += 1
    return count

colors = [0, 1, 0, 1, 0]
k = 3
print(count_alternating_groups(colors, k))

Java

public class Main {
    public static int countAlternatingGroups(int[] colors, int k) {
        int n = colors.length;
        int count = 0;
        for (int i = 0; i < n; i++) {
            boolean valid = true;
            for (int j = 1; j < k; j++) {
                if (colors[(i + j) % n] == colors[(i + j - 1) % n]) {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[] colors = {0, 1, 0, 1, 0};
        int k = 3;
        System.out.println(countAlternatingGroups(colors, k));
    }
}

C++

#include <vector>
#include <iostream>
using namespace std;

int countAlternatingGroups(vector<int>& colors, int k) {
    int n = colors.size();
    int count = 0;
    for (int i = 0; i < n; i++) {
        bool valid = true;
        for (int j = 1; j < k; j++) {
            if (colors[(i + j) % n] == colors[(i + j - 1) % n]) {
                valid = false;
                break;
            }
        }
        if (valid) count++;
    }
    return count;
}

int main() {
    vector<int> colors = {0, 1, 0, 1, 0};
    int k = 3;
    cout << countAlternatingGroups(colors, k) << endl;
    return 0;
}

JavaScript

function countAlternatingGroups(colors, k) {
    const n = colors.length;
    let count = 0;
    for (let i = 0; i < n; i++) {
        let valid = true;
        for (let j = 1; j < k; j++) {
            if (colors[(i + j) % n] === colors[(i + j - 1) % n]) {
                valid = false;
                break;
            }
        }
        if (valid) {
            count++;
        }
    }
    return count;
}

const colors = [0, 1, 0, 1, 0];
const k = 3;
console.log(countAlternatingGroups(colors, k));

#include <stdio.h>

int countAlternatingGroups(int* colors, int colorsSize, int k) {
    int count = 0;
    for (int i = 0; i < colorsSize; i++) {
        int valid = 1;
        for (int j = 1; j < k; j++) {
            if (colors[(i + j) % colorsSize] == colors[(i + j - 1) % colorsSize]) {
                valid = 0;
                break;
            }
        }
        if (valid) count++;
    }
    return count;
}

int main() {
    int colors[] = {0, 1, 0, 1, 0};
    int k = 3;
    printf("%d\n", countAlternatingGroups(colors, 5, k));
    return 0;
}

using System;

class Program {
    static int CountAlternatingGroups(int[] colors, int k) {
        int n = colors.Length;
        int count = 0;
        for (int i = 0; i < n; i++) {
            bool valid = true;
            for (int j = 1; j < k; j++) {
                if (colors[(i + j) % n] == colors[(i + j - 1) % n]) {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                count++;
            }
        }
        return count;
    }

    static void Main() {
        int[] colors = {0, 1, 0, 1, 0};
        int k = 3;
        Console.WriteLine(CountAlternatingGroups(colors, k));
    }
}

The Python solution uses a looping structure with modulo indexing to efficiently check each k-length subarray of a circular array for the alternating property.

Complexity

Time Complexity: O(n * k).

Space Complexity: O(1).

Try this approach in the editor

Approach 2: Pattern Recognition with Auxiliary Array

This approach initiates by preprocessing the colors array to recognize blocks of alternating patterns and storing them into an auxiliary array. This allows faster evaluation of k-sized blocks by looking up preprocessed boundaries directly in the auxiliary array.

Python

def count_alternating_groups(colors, k):
    n = len(colors)
    pattern = [1] * n
    count = 0

    for i in range(n):
        if colors[i] == colors[(i + 1) % n]:
            pattern[i] = 0

    for i in range(n):
        valid = True
        for j in range(k):
            if pattern[(i + j) % n] == 0:
                valid = False
                break
        if valid:
            count += 1

    return count

colors = [0, 1, 0, 1, 0]
k = 3
print(count_alternating_groups(colors, k))

Java

import java.util.Arrays;

public class Main {
    public static int countAlternatingGroups(int[] colors, int k) {
        int n = colors.length;
        int[] pattern = new int[n];
        Arrays.fill(pattern, 1);
        int count = 0;

        for (int i = 0; i < n; i++) {
            if (colors[i] == colors[(i + 1) % n]) {
                pattern[i] = 0;
            }
        }

        for (int i = 0; i < n; i++) {
            boolean valid = true;
            for (int j = 0; j < k; j++) {
                if (pattern[(i + j) % n] == 0) {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                count++;
            }
        }

        return count;
    }

    public static void main(String[] args) {
        int[] colors = {0, 1, 0, 1, 0};
        int k = 3;
        System.out.println(countAlternatingGroups(colors, k));
    }
}

C++

#include <vector>
#include <iostream>
using namespace std;

int countAlternatingGroups(vector<int>& colors, int k) {
    int n = colors.size();
    vector<int> pattern(n, 1);
    int count = 0;

    for (int i = 0; i < n; i++) {
        if (colors[i] == colors[(i + 1) % n]) {
            pattern[i] = 0;
        }
    }

    for (int i = 0; i < n; i++) {
        bool valid = true;
        for (int j = 0; j < k; j++) {
            if (pattern[(i + j) % n] == 0) {
                valid = false;
                break;
            }
        }
        if (valid) count++;
    }

    return count;
}

int main() {
    vector<int> colors = {0, 1, 0, 1, 0};
    int k = 3;
    cout << countAlternatingGroups(colors, k) << endl;
    return 0;
}

JavaScript

function countAlternatingGroups(colors, k) {
    const n = colors.length;
    const pattern = Array(n).fill(1);
    let count = 0;

    for (let i = 0; i < n; i++) {
        if (colors[i] === colors[(i + 1) % n]) {
            pattern[i] = 0;
        }
    }

    for (let i = 0; i < n; i++) {
        let valid = true;
        for (let j = 0; j < k; j++) {
            if (pattern[(i + j) % n] === 0) {
                valid = false;
                break;
            }
        }
        if (valid) {
            count++;
        }
    }

    return count;
}

const colors = [0, 1, 0, 1, 0];
const k = 3;
console.log(countAlternatingGroups(colors, k));

#include <stdio.h>
#include <stdbool.h>

int countAlternatingGroups(int* colors, int colorsSize, int k) {
    int pattern[colorsSize];
    int count = 0;
    bool isPattern = true;
    int j = 0;

    for (int i = 0; i < colorsSize; i++) {
        if (colors[i] == colors[(i + 1) % colorsSize]) {
            isPattern = false;
        }
        pattern[j++] = isPattern ? 1 : 0;
    }

    for (int i = 0; i < colorsSize; i++) {
        bool valid = true;
        for (j = 0; j < k; j++) {
            if (pattern[(i + j) % colorsSize] == 0) {
                valid = false;
                break;
            }
        }
        if (valid) count++;
    }

    return count;
}

int main() {
    int colors[] = {0, 1, 0, 1, 0};
    int k = 3;
    printf("%d\n", countAlternatingGroups(colors, 5, k));
    return 0;
}

using System;

class Program {
    static int CountAlternatingGroups(int[] colors, int k) {
        int n = colors.Length;
        int[] pattern = new int[n];
        Array.Fill(pattern, 1);
        int count = 0;

        for (int i = 0; i < n; i++) {
            if (colors[i] == colors[(i + 1) % n]) {
                pattern[i] = 0;
            }
        }

        for (int i = 0; i < n; i++) {
            bool valid = true;
            for (int j = 0; j < k; j++) {
                if (pattern[(i + j) % n] == 0) {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                count++;
            }
        }

        return count;
    }

    static void Main() {
        int[] colors = {0, 1, 0, 1, 0};
        int k = 3;
        Console.WriteLine(CountAlternatingGroups(colors, k));
    }
}

The Python approach creates a pattern array upon preprocessing to highlight valid starting indices for possible groups, streamlining future calculations.

Complexity

Time Complexity: O(n * k).

Space Complexity: O(n).

Try this approach in the editor

Approach 3: Single Pass

We can unfold the ring into an array of length 2n and then traverse this array from left to right. We use a variable cnt to record the current length of the alternating group. If we encounter the same color, we reset cnt to 1; otherwise, we increment cnt. If cnt \ge k and the current position i is greater than or equal to n, then we have found an alternating group, and we increment the answer by one.

After the traversal, we return the answer.

The time complexity is O(n), where n is the length of the array colors. The space complexity is O(1).

TypeScript

function numberOfAlternatingGroups(colors: number[], k: number): number {
    const n = colors.length;
    let [ans, cnt] = [0, 0];
    for (let i = 0; i < n << 1; ++i) {
        if (i && colors[i % n] === colors[(i - 1) % n]) {
            cnt = 1;
        } else {
            ++cnt;
        }
        ans += i >= n && cnt >= k ? 1 : 0;
    }
    return ans;
}

func numberOfAlternatingGroups(colors []int, k int) (ans int) {
	n := len(colors)
	cnt := 0
	for i := 0; i < n<<1; i++ {
		if i > 0 && colors[i%n] == colors[(i-1)%n] {
			cnt = 1
		} else {
			cnt++
		}
		if i >= n && cnt >= k {
			ans++
		}
	}
	return
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Sliding Window Approach	Time Complexity: O(n * k). Space Complexity: O(1).
Pattern Recognition with Auxiliary Array	Time Complexity: O(n * k). Space Complexity: O(n).
Single Pass	–

Approach

Complexity

Sliding Window Approach

Time Complexity: O(n * k).

Space Complexity: O(1).

Pattern Recognition with Auxiliary Array

Time Complexity: O(n * k).

Space Complexity: O(n).

Single Pass

–

Complexity analysis

Approach	Time	Space	When to Use
Sliding Window on Alternation Count	O(n)	O(1)	Best general solution. Efficient for large arrays and commonly expected in interviews.
Auxiliary Alternation Array + Sliding Window	O(n)	O(n)	Useful when separating pattern detection from counting improves clarity or debugging.

Frequently asked questions

Is Alternating Groups II easy or hard?

Alternating Groups II is rated Medium. The main challenge is handling the circular array and recognizing that a group of k elements depends on k-1 alternating neighbor comparisons. Once that insight is clear, a linear-time sliding window solution becomes straightforward.

Alternating Groups II Python/Java solution

Most implementations iterate through the circular array and maintain a sliding window that tracks alternating edges. The logic is identical across Python, Java, C++, and other languages: update the window state as you move forward and increment the count whenever k tiles satisfy the alternating condition.

How to solve Alternating Groups II in O(n)?

Track whether adjacent tiles alternate and maintain a sliding window representing k consecutive tiles. A group is valid when the window contains exactly k-1 alternating edges. Update the window as you move forward across the circular array using modulo indexing to handle wrap-around.

What is the best approach for Alternating Groups II?

The best approach uses a sliding window to track whether each group of k tiles maintains alternating neighbors. A valid group requires k-1 alternating edges. By updating the window incrementally while traversing the circular array, you count valid groups in O(n) time with O(1) extra space.

Is Alternating Groups II asked at Google/Amazon/Meta?

Alternating pattern and sliding window problems frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the technique of counting valid windows based on adjacency conditions is a common interview pattern.

What data structure is used in Alternating Groups II?

The core data structure is an array combined with a sliding window technique. Some implementations also use an auxiliary array to store whether adjacent elements alternate, which simplifies pattern detection before applying the window.

What is the time complexity of Alternating Groups II?

The optimal solution runs in O(n) time where n is the number of tiles in the colors array. Each element is processed a constant number of times while maintaining the sliding window. Space complexity can be O(1) with direct window tracking or O(n) if an auxiliary array is used.

Alternating Groups II solution and explanation

The problem

Approach overview

Approach 1: Sliding Window Approach

Approach 2: Pattern Recognition with Auxiliary Array

Approach 3: Single Pass

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Alternating Groups II solution and explanation

The problem

Approach overview

Approach 1: Sliding Window Approach

Approach 2: Pattern Recognition with Auxiliary Array

Approach 3: Single Pass

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems