We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Alternating Groups II

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem requires identifying segments of k contiguous tiles that alternate in color.
  • The circular nature of the tiles means that we need to consider the last tiles connecting back to the first tiles.
  • A sliding window approach can efficiently check each group of k tiles for the alternating condition.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The solution uses a sliding window technique to iterate through the array of colors while checking for alternating patterns. We maintain a count of valid groups as we check each segment of k tiles. Since the list is circular, we wrap around the index when reaching the end of the array.

Code Solutions

def countAlternatingGroups(colors, k):
    n = len(colors)
    count = 0
    
    # Iterate through the array to check each group of size k
    for i in range(n):
        valid = True
        
        # Check if the current window of size k is alternating
        for j in range(k):
            # Check the current tile with the next tile in the group
            if colors[(i + j) % n] == colors[(i + j + 1) % n]:
                valid = False
                break
        
        if valid:
            count += 1
            
    return count
← Back to All Questions