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

Number of Adjacent Elements With the Same Color

Number: 2779

Difficulty: Medium

Paid? No

Companies: Roblox

Problem Description

Given an integer n representing the length of an array colors (initialized with zeros, meaning uncolored) and a list of queries where each query provides an index and a new color, update the array at the specified index with the new color. After each query, count the number of adjacent pairs in the array that have the same color. Return an array where each element is the count after processing the respective query.

Key Insights

  • The initial array is uncolored (all zeros); we only start counting adjacent pairs when elements are colored (non-zero).
  • A brute-force recount of adjacent pairs after each query would be inefficient for large n and many queries.
  • Instead, maintain a running count of adjacent matching pairs.
  • For each query, only the pairs involving the updated index might change — check the left neighbor and the right neighbor.
  • Before updating, subtract the contribution of the current color (if any) with its neighbors, then update the color and add the new contributions.
  • This allows each query to be processed in constant time.

Space and Time Complexity

Time Complexity: O(1) per query, resulting in O(q) overall where q is the number of queries. Space Complexity: O(n) for storing the colors array.

Solution

We maintain an array (or list) called colors to track the current color of each element. Also, keep a variable count to store the current number of adjacent pairs with the same color.

For each query:

  1. Read the index and the new color.
  2. Check the element's left neighbor (if exists):
    • If the previous color at index and its left neighbor matched, decrement the count.
  3. Check the element's right neighbor (if exists):
    • If the previous color at index and its right neighbor matched, decrement the count.
  4. Update the value at the specified index.
  5. Again, check the updated index’s left neighbor:
    • If the new color matches with the left neighbor, increment the count.
  6. Similarly, check the right neighbor:
    • If the new color matches with the right neighbor, increment the count.
  7. Append the current count to the result after processing the query.

This method uses local adjustments to the count based on the neighbors and processes each query in constant time while using O(n) additional space for the colors array.

Code Solutions

# Python solution with line-by-line comments

def countAdjacentPairs(n, queries):
    # Initialize the colored array with 0's (uncolored)
    colors = [0] * n
    # Initialize count of adjacent pairs with same color
    adjacent_count = 0
    # List to store answer after each query
    result = []
    
    for index, new_color in queries:
        # If already assigned a color, remove its previous contribution with neighbors
        old_color = colors[index]
        # Check left neighbor if exists and was contributing to the previous count
        if index - 1 >= 0 and colors[index - 1] == old_color and old_color != 0:
            adjacent_count -= 1
        # Check right neighbor if exists and was contributing to the previous count
        if index + 1 < n and colors[index + 1] == old_color and old_color != 0:
            adjacent_count -= 1
        
        # Set the new color at the given index
        colors[index] = new_color
        
        # Check left neighbor for new match and update count if necessary
        if index - 1 >= 0 and colors[index - 1] == new_color and new_color != 0:
            adjacent_count += 1
        # Check right neighbor for new match and update count if necessary
        if index + 1 < n and colors[index + 1] == new_color and new_color != 0:
            adjacent_count += 1

        # Append the current count to the results list
        result.append(adjacent_count)
        
    return result

# Example usage:
if __name__ == "__main__":
    n = 4
    queries = [[0,2],[1,2],[3,1],[1,1],[2,1]]
    print(countAdjacentPairs(n, queries))  # expected output: [0, 1, 1, 0, 2]
← Back to All Questions