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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Alternating Groups II

Number: 3483

Difficulty: Medium

Paid? No

Companies: Google, Microsoft, Samsara

Problem Description

Given a circular array of tiles where each tile is either red (0) or blue (1), and an integer k, count the number of contiguous groups of k tiles (considering the circular connection) that are “alternating”. A group is alternating if, for every pair of adjacent tiles within it, the colors are different.

Key Insights

  • The circular nature requires us to consider the wrap-around when checking groups.
  • For a contiguous group of k tiles to be alternating, each adjacent pair (from the start to the end of the group) must have different colors.
  • Precompute an array (diff) where each element indicates if a tile and its next neighbor (using modulo for the last tile) are of different colors.
  • Use a sliding window over the diff array (of length k­–1 for each group) to quickly determine if all consecutive pairs in a group are alternating.
  • Extending the diff array (or using modulo arithmetic) simplifies handling the circular wrap-around.

Space and Time Complexity

Time Complexity: O(n), where n is the number of tiles, since each tile is processed a constant number of times. Space Complexity: O(n) due to the auxiliary diff array (or O(1) if using in-place modulo arithmetic with careful indexing).

Solution

We start by computing an auxiliary diff array of size n, where diff[i] is 1 if tile i and tile (i+1 mod n) have different colors, else 0. For a group of k tiles starting at index i, we need to check if the sum of diff[i] over the next k–1 entries equals k–1 (i.e. every adjacent pair is alternating).

Because the tiles are arranged in a circle, when the window reaches the end of the diff array, we wrap around by either concatenating diff with itself or using modulo arithmetic to update the sliding sum. We then count the number of windows (each representing a group) that satisfy the alternating condition.

The solution uses the sliding window technique so that we update the sum efficiently by subtracting the element that leaves the window and adding the new element that enters.

Code Solutions

Below are implementations in Python, JavaScript, C++, and Java.

# Python solution using sliding window
def alternatingGroupsII(colors, k):
    n = len(colors)
    # create diff array where diff[i] = 1 if colors[i] != colors[(i+1)%n], else 0
    diff = [1 if colors[i] != colors[(i+1) % n] else 0 for i in range(n)]
    
    # The window length needed is k-1 differences in order for k tiles to be alternating.
    window_length = k - 1
    total_groups = 0
    
    # Build initial window sum over the first window with wrapping using extended diff array approach.
    # Instead of creating an extended array explicitly, we simulate it.
    curr_sum = 0
    for i in range(window_length):
        curr_sum += diff[i % n]
    
    if curr_sum == window_length:
        total_groups += 1
    
    # Slide the window for all starting positions from 1 to n-1.
    for i in range(1, n):
        # Remove the element that is leaving the window and add the new element entering the window.
        curr_sum -= diff[(i - 1) % n]
        curr_sum += diff[(i + window_length - 1) % n]
        if curr_sum == window_length:
            total_groups += 1
    
    return total_groups

# Example usage:
print(alternatingGroupsII([0,1,0,1,0], 3))  # Expected output: 3
← Back to All Questions