Scale Engineer

Alternating Groups I

Easy
#2847Time: O(n), where n is the number of tiles. We perform one pass to create the extended array and another pass to count the groups.Space: O(n), as we create an auxiliary array of size n + 2 to store the extended sequence of colors.1 company
Patterns
Sliding Window
Data structures
Array
Companies
Samsara

Prompt

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 that since colors represents a circle, the first and the last tiles are considered to be next to each other.

 

Example 1:

Input: colors = [1,1,1]

Output: 0

Explanation:

Example 2:

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

Output: 3

Explanation:

Alternating groups:

 

Constraints:

  • 3 <= colors.length <= 100
  • 0 <= colors[i] <= 1

Approaches

2 approaches with complexity analysis and trade-offs.

This approach simplifies handling the circular nature of the tile arrangement by creating a new, larger array. We append the first two elements of the original array to its end. This allows us to iterate through the groups of three using standard linear indexing without special checks for wrap-around cases.

Algorithm

  • Let n be the number of tiles in the colors array.
  • Create a new integer array, extendedColors, of size n + 2.
  • Copy the elements from the original colors array into extendedColors.
  • To handle the circularity, append the first two elements of colors to the end of extendedColors. So, extendedColors[n] becomes colors[0], and extendedColors[n+1] becomes colors[1].
  • Initialize a counter, count, to zero.
  • Iterate from i = 1 to n. The element extendedColors[i] corresponds to the middle tile of a group. The loop covers all n possible groups from the original circular arrangement.
  • For each i, check if extendedColors[i] has a different color from its neighbors, extendedColors[i-1] and extendedColors[i+1].
  • If extendedColors[i] != extendedColors[i-1] and extendedColors[i] != extendedColors[i+1], increment the count.
  • After the loop completes, count will hold the total number of alternating groups. Return count.

Walkthrough

This approach works by creating a temporary, extended array to handle the circular property of the tiles, which simplifies the iteration logic. By creating a new array extendedColors of size n+2 and appending colors[0] and colors[1] to the end of the original colors array, we can treat the circular array as a linear one. We can then iterate from the second element to the (n+1)-th element of this new array, checking each triplet (extendedColors[i-1], extendedColors[i], extendedColors[i+1]) for the alternating property. This avoids complex index calculations like modulo or conditional checks within the loop.

class Solution {    public int numberOfAlternatingGroups(int[] colors) {        int n = colors.length;                // Create an extended array to simplify boundary checks        int[] extendedColors = new int[n + 2];        for (int i = 0; i < n; i++) {            extendedColors[i] = colors[i];        }        extendedColors[n] = colors[0];        extendedColors[n+1] = colors[1];                int count = 0;        // Iterate through the original n possible middle elements        // The window [i-1, i, i+1] in extendedColors corresponds to a group in the circle        for (int i = 1; i <= n; i++) {            if (extendedColors[i] != extendedColors[i - 1] && extendedColors[i] != extendedColors[i + 1]) {                count++;            }        }                return count;    }}

Complexity

Time

O(n), where n is the number of tiles. We perform one pass to create the extended array and another pass to count the groups.

Space

O(n), as we create an auxiliary array of size n + 2 to store the extended sequence of colors.

Trade-offs

Pros

  • Simpler loop logic by avoiding explicit modulo operations or conditional checks for wrap-around indices.

Cons

  • Uses extra space proportional to the input size, which is less efficient than an in-place approach.

Solutions

class Solution {public  int numberOfAlternatingGroups(int[] colors) {    int k = 3;    int n = colors.length;    int ans = 0, cnt = 0;    for (int i = 0; i < n << 1; ++i) {      if (i > 0 && colors[i % n] == colors[(i - 1) % n]) {        cnt = 1;      } else {        ++cnt;      }      ans += i >= n && cnt >= k ? 1 : 0;    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem