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

Number of Adjacent Elements With the Same Color

Difficulty: Medium

Problem Description

You are given an integer n representing an array colors of length n where all elements are set to 0's meaning uncolored. You are also given a 2D integer array queries where queries[i] = [index_i, color_i]. For the i-th query:

  • Set colors[index_i] to color_i.
  • Count adjacent pairs in colors set to the same color (regardless of color_i).

Return an array answer of the same length as queries where answer[i] is the answer to the i-th query.

Key Insights

  • The adjacent elements need to be counted only when they have the same color.
  • The state of the array changes with each query, and the result for each query depends on the previous state.
  • Efficiently managing the color changes and counting adjacent pairs is crucial to meet the time complexity constraints.

Space and Time Complexity

Time Complexity: O(q) for processing each query, with O(1) time for counting adjacent pairs during each update. Therefore, the overall complexity is O(n + q). Space Complexity: O(n) for storing the colors array.

Solution

To solve the problem, we will use an array to represent the colors. As we process each query, we will:

  1. Check if the color at the specified index is already the same as the new color. If so, we can skip the update.
  2. If the color is changed:
    • Check the left and right neighbors of the index to see if they were the same color before the change. Adjust the count of adjacent pairs accordingly.
    • Update the color at the specified index.
    • Check again the left and right neighbors after the update to adjust the count of adjacent pairs.
  3. Store the result after each query.

This approach ensures that we only check the relevant indices around the updated index, making it efficient.

Code Solutions

def numAdjacentElements(n, queries):
    colors = [0] * n
    adjacent_count = 0
    answer = []
    
    for index, color in queries:
        # Update adjacent_count if needed
        if colors[index] == color:
            answer.append(adjacent_count)
            continue
        
        # Check left neighbor
        if index > 0 and colors[index] == colors[index - 1]:
            adjacent_count -= 1
        if index > 0 and color == colors[index - 1]:
            adjacent_count += 1
            
        # Check right neighbor
        if index < n - 1 and colors[index] == colors[index + 1]:
            adjacent_count -= 1
        if index < n - 1 and color == colors[index + 1]:
            adjacent_count += 1
        
        # Update the color
        colors[index] = color
        
        answer.append(adjacent_count)
    
    return answer
← Back to All Questions