Alternating Groups I - Solution & Explanation

Problem Overview: You are given a circular colors array where each value represents a tile color. A group is valid if three consecutive tiles form an alternating pattern (for example 0,1,0 or 1,0,1). Because the array is circular, the sequence can wrap from the end back to the start. The task is to count how many length-3 groups satisfy this alternating rule.

Approach 1: Iterative Pattern Check (O(n) time, O(1) space)

Iterate through every index i and examine the next two elements using circular indexing. A valid alternating group occurs when colors[i] != colors[i+1] and colors[i+1] != colors[i+2]. These two comparisons guarantee the pattern flips at each step. Use modulo arithmetic to wrap indices: (i + 1) % n and (i + 2) % n. This approach simply scans the array once, performs constant comparisons per index, and increments a counter when the condition holds. The logic is straightforward and works well when the group size is fixed.

This technique relies purely on sequential iteration over the array. Since only three values are inspected at a time, memory usage stays constant and the runtime grows linearly with the number of tiles.

Approach 2: Sliding Window (O(n) time, O(1) space)

A more general way to reason about the problem is with a fixed-size sliding window of length 3. Start with the first three elements and verify whether they alternate. Then slide the window forward by one position at a time while maintaining circular indexing. Each shift removes the leftmost element and includes the next element in the circle.

The key insight is that the window validity depends only on two adjacent comparisons: a != b and b != c. Every time the window moves, recompute these comparisons for the new triplet. Because the window size never changes, each step performs constant work. The circular property is handled by indexing with modulo so the window naturally wraps from the last element to the first.

This method is conceptually useful because it mirrors how many larger alternating-pattern problems are solved. When group sizes become variable or constraints increase, the sliding window pattern scales better than hardcoding comparisons.

Recommended for interviews: The sliding window explanation is typically preferred. Interviewers expect you to recognize the alternating constraint as a local window property and scan the array in O(n) time with constant memory. The direct iteration solution also runs in linear time and clearly demonstrates understanding, but framing it as a window problem shows stronger familiarity with common algorithm patterns.