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 III

Number: 3527

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

We are given a circular array of tiles where each tile is colored either red (0) or blue (1). We need to answer two kinds of queries:

  1. Query [1, k]: Count the number of contiguous “alternating” groups (subarrays) of size k. An alternating group is one in which every adjacent pair of tiles has different colors.
  2. Query [2, index, color]: Update the tile at position index to the new color. Note that because the tiles are arranged in a circle, the first and the last tiles are adjacent.

Key Insights

  • When determining if a contiguous subarray is alternating, what matters is whether every adjacent pair changes color.
  • Define a helper array diff where diff[i] = 1 if colors[i] and colors[(i+1) mod n] are different and 0 otherwise.
  • A window (subarray) of size k is alternating if the sum of diff over the k-1 consecutive positions (starting at some index i) equals k-1.
  • Updates only affect boundaries: updating colors[i] changes diff[(i-1+n) mod n] and diff[i].
  • Efficient query handling can be done by using data structures (such as Binary Indexed Trees or segment trees) that support range sum queries and point updates.
  • An alternative “segment‐merging” idea is to maintain the contiguous blocks (segments) of alternating tiles. For a segment of length L (the number of “diff” ones is L–1), the number of alternating groups of size k that lie completely in it is max(0, L – k + 1). Special care is needed if the entire circle is alternating (in which case two ends merge).

Space and Time Complexity

Time Complexity: O((n + q) * log n) per query in an optimized solution (using a BIT or segment tree) where n is the number of tiles and q is the number of queries. Space Complexity: O(n)

Solution

The idea is to maintain an ancillary structure (for example, a Binary Indexed Tree (BIT)) over a helper array that tracks where adjacent tiles alternate. Let diff[i] = 1 if colors[i] and colors[(i+1) mod n] differ; otherwise, diff[i] = 0.

For a query “[1, k]”, an alternating group of size k starting at position i exists if the sum over diff from index i to i+k–2 (taking modulo arithmetic for the circular array) equals k–1. Thus, the answer is the number of starting positions i (from 0 to n–1) that satisfy that condition.

For an update query “[2, index, color]”, we update the colors array and adjust diff at two positions: at index (index–1+n) mod n (between the previous tile and the updated tile) and at index index (between the updated tile and its next neighbor). The BIT is then updated accordingly.

There are multiple ways to implement this solution. One may choose a BIT to support point updates in diff as well as range queries over diff. In the provided code solutions below each query is handled by updating the BIT when needed and for query type 1, scanning over possible starting indices using BIT range queries (using a doubled structure to manage circular wrap‐around). Note that while the naive scanning over all starting indices is O(n log n) per query, careful preprocessing (or a segment–merging approach) can reduce constant factors. The code below is written in a clear, language–agnostic manner with line–by–line comments.

Code Solutions

# Python solution using Binary Indexed Tree (Fenwick Tree)
class FenwickTree:
    def __init__(self, size):
        self.n = size
        self.tree = [0] * (size + 1)
    
    # Update the BIT: add delta at index i (0-indexed)
    def update(self, i, delta):
        i += 1  # shift to 1-indexed
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i

    # Query prefix sum [0, i]
    def query(self, i):
        s = 0
        i += 1  # shift to 1-indexed
        while i:
            s += self.tree[i]
            i -= i & -i
        return s
    
    # Range sum query [l, r]
    def range_query(self, l, r):
        return self.query(r) - (self.query(l - 1) if l > 0 else 0)


class AlternatingGroups:
    def __init__(self, colors):
        self.colors = colors
        self.n = len(colors)
        # Build diff: diff[i] = 1 if colors[i] != colors[(i+1)%n]
        self.diff = [0] * self.n
        for i in range(self.n):
            next_i = (i + 1) % self.n
            self.diff[i] = 1 if self.colors[i] != self.colors[next_i] else 0
        # Build BIT on diff; we use BIT on 2*n elements to handle circular queries
        self.size = self.n * 2
        self.bit = FenwickTree(self.size)
        for i in range(self.size):
            # Use diff[i % n] for doubled array
            self.bit.update(i, self.diff[i % self.n])
    
    # Update color at index and adjust diff
    def update_color(self, index, new_color):
        # If no change, return early.
        if self.colors[index] == new_color:
            return
        self.colors[index] = new_color
        n = self.n
        # Positions in diff that change: index-1 and index (taking mod n)
        affected = [ (index - 1) % n, index ]
        for pos in affected:
            old_val = self.diff[pos]
            next_index = (pos + 1) % n
            new_val = 1 if self.colors[pos] != self.colors[next_index] else 0
            if old_val != new_val:
                self.diff[pos] = new_val
                # Update both positions in BIT (in the original and the copy)
                for base in [0, n]:
                    self.bit.update(pos + base, new_val - old_val)
    
    # Count alternating groups of size group_size.
    # A valid group starting at i exists if the BIT query over indices [i, i+group_size-2] equals group_size-1.
    def count_groups(self, group_size):
        count = 0
        required = group_size - 1
        n = self.n
        # We iterate over starting indices 0 to n-1
        for start in range(n):
            end = start + group_size - 2  # inclusive index in doubled array
            # Query BIT from start to end in O(log n)
            s = self.bit.range_query(start, end)
            if s == required:
                count += 1
        return count

def processQueries(colors, queries):
    ag = AlternatingGroups(colors)
    results = []
    for query in queries:
        if query[0] == 1:
            # Count query: query = [1, group_size]
            group_size = query[1]
            results.append(ag.count_groups(group_size))
        else:
            # Update query: query = [2, index, new_color]
            index, new_color = query[1], query[2]
            ag.update_color(index, new_color)
    return results

# Example usage:
colors = [0,1,1,0,1]
queries = [[2,1,0],[1,4]]
print(processQueries(colors, queries))  # Expected output: [2]
← Back to All Questions