Problem Description

You start with an array of length n where all elements are initially 0 (representing uncolored positions). You're given a series of queries, where each query contains an index and a color value.

For each query [index, color], you need to:

1. Color the element at the given index with the specified color (set colors[index] = color)
2. Count how many adjacent pairs in the entire array have the same color after this coloring

An adjacent pair means two consecutive elements in the array (elements at positions i and i+1). Two adjacent elements form a matching pair if they have the same color value, and that color is not 0 (uncolored elements don't count as matching).

The solution tracks the number of matching adjacent pairs efficiently by:

• Before changing a position's color, it checks if that position currently forms matching pairs with its neighbors (left and right), and decreases the count accordingly
• After assigning the new color, it checks if the new color creates matching pairs with its neighbors and increases the count
• The variable x maintains the running count of matching adjacent pairs
• For each query, the current count is stored in the answer array

For example, if you have an array [1, 1, 2, 0, 0], there is exactly 1 matching adjacent pair (the two 1's at positions 0 and 1). If you then color position 2 with color 1, the array becomes [1, 1, 1, 0, 0] and you now have 2 matching adjacent pairs.

The function returns an array where each element represents the total number of matching adjacent pairs after processing each query in order.

Intuition

The key insight is that when we color a position, we only need to consider how this change affects the adjacent pairs involving that specific position - not the entire array. Each position can form at most two adjacent pairs: one with its left neighbor and one with its right neighbor.

When we update colors[i] to a new color, we're potentially changing two adjacent pairs:

• The pair (colors[i-1], colors[i])
• The pair (colors[i], colors[i+1])

Instead of recounting all adjacent pairs from scratch after each query (which would be O(n) per query), we can maintain a running count and just update it based on the local changes.

The approach is to:

1. Remove the old contributions: Before changing colors[i], check if the current value forms any matching pairs with its neighbors. If it does, we need to subtract these from our count since they won't exist after the change.
2. Add the new contributions: After setting the new color, check if this new color creates any matching pairs with the neighbors and add these to our count.

This incremental update strategy is efficient because:

• We only examine at most 2 positions (the left and right neighbors) per query
• We maintain the global count x throughout all queries, updating it incrementally
• Each query takes O(1) time instead of O(n)

The careful handling of boundary conditions (when i = 0 or i = n-1) and checking that colors are non-zero (since 0 represents uncolored) ensures we count only valid matching pairs.

Solution Approach

The solution uses a simulation approach with incremental updates to efficiently track the number of matching adjacent pairs.

Data Structures:

• nums: An array of size n initialized with zeros to represent the current state of colors
• ans: Result array to store the count of matching pairs after each query
• x: A running counter that maintains the current number of matching adjacent pairs

Algorithm Implementation:

For each query (i, c) where we need to color position i with color c:

1. Remove contributions from the old color at position i:

   • Check left neighbor: If i > 0 and nums[i] != 0 and nums[i-1] == nums[i], decrement x by 1
   • Check right neighbor: If i < n-1 and nums[i] != 0 and nums[i+1] == nums[i], decrement x by 1

   These checks ensure we only decrement when there's an existing matching pair that will be broken.

2. Add contributions from the new color c:

   • Check left neighbor: If i > 0 and nums[i-1] == c, increment x by 1
   • Check right neighbor: If i < n-1 and nums[i+1] == c, increment x by 1

   These checks determine if the new color will create matching pairs with neighbors.

3. Update and record:

   • Store the current value of x in ans[k] for the k-th query
   • Update nums[i] = c to reflect the new color

The order of operations is crucial: we must update the count before actually changing the color in the array, otherwise we'd lose information about the previous state.

Time Complexity: O(m) where m is the number of queries, since each query processes in O(1) time.

Space Complexity: O(n) for the nums array and O(m) for the answer array.

Example Walkthrough

Let's walk through a concrete example with n = 5 and queries [[1,2], [2,2], [0,1], [3,1]].

Initial State:

• Array: [0, 0, 0, 0, 0]
• Matching pairs count x = 0

Query 1: [1, 2] - Color position 1 with color 2

• Check position 1's current contributions:
  • Left neighbor (position 0): nums[1] = 0, so no existing pair to remove
  • Right neighbor (position 2): nums[1] = 0, so no existing pair to remove
• Apply new color 2 at position 1:
  • Left neighbor check: nums[0] = 0 ≠ 2, no new pair
  • Right neighbor check: nums[2] = 0 ≠ 2, no new pair
• Update: nums[1] = 2, x = 0
• Array: [0, 2, 0, 0, 0], Answer: [0]

Query 2: [2, 2] - Color position 2 with color 2

• Check position 2's current contributions:
  • Left neighbor (position 1): nums[2] = 0, so no existing pair to remove
  • Right neighbor (position 3): nums[2] = 0, so no existing pair to remove
• Apply new color 2 at position 2:
  • Left neighbor check: nums[1] = 2 = 2, creates a new pair! x++
  • Right neighbor check: nums[3] = 0 ≠ 2, no new pair
• Update: nums[2] = 2, x = 1
• Array: [0, 2, 2, 0, 0], Answer: [0, 1]

Query 3: [0, 1] - Color position 0 with color 1

• Check position 0's current contributions:
  • No left neighbor (boundary)
  • Right neighbor (position 1): nums[0] = 0, so no existing pair to remove
• Apply new color 1 at position 0:
  • No left neighbor to check
  • Right neighbor check: nums[1] = 2 ≠ 1, no new pair
• Update: nums[0] = 1, x = 1
• Array: [1, 2, 2, 0, 0], Answer: [0, 1, 1]

Query 4: [3, 1] - Color position 3 with color 1

• Check position 3's current contributions:
  • Left neighbor (position 2): nums[3] = 0, so no existing pair to remove
  • Right neighbor (position 4): nums[3] = 0, so no existing pair to remove
• Apply new color 1 at position 3:
  • Left neighbor check: nums[2] = 2 ≠ 1, no new pair
  • Right neighbor check: nums[4] = 0 ≠ 1, no new pair
• Update: nums[3] = 1, x = 1
• Array: [1, 2, 2, 1, 0], Answer: [0, 1, 1, 1]

Final Result: [0, 1, 1, 1]

The array [1, 2, 2, 1, 0] has exactly one matching adjacent pair: positions 1 and 2 both have color 2.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m) where m is the length of queries.

The algorithm iterates through each query exactly once. For each query, it performs a constant number of operations:

• Checking and updating at most 2 adjacent positions (left and right neighbors)
• Each check involves simple comparisons and arithmetic operations (O(1))
• Updating the array at position i and the answer array

Since we process m queries and each query takes O(1) time, the total time complexity is O(m).

Space Complexity: O(n + m) where n is the size of the array and m is the length of queries.

The space usage consists of:

• nums array: O(n) space to store the current state of the array
• ans array: O(m) space to store the result for each query
• Variable x: O(1) space for tracking the current count of adjacent same-color pairs
• Loop variables: O(1) space

The total auxiliary space used is O(n + m). If we only consider extra space beyond the output array ans, then the auxiliary space complexity would be O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Updating the Array Before Adjusting the Count

One of the most common mistakes is updating colors[position] = new_color before calculating the changes to the adjacent pair count. This destroys the information about the previous color, making it impossible to correctly determine which pairs need to be removed from the count.

Incorrect approach:

# WRONG: Updating color first
colors[position] = new_color  # This loses the old color information!

# Now we can't properly check what pairs existed before
if position > 0 and old_color_we_lost == colors[position - 1]:
    adjacent_same_color_count -= 1

Correct approach:

# RIGHT: Calculate changes first, then update
# Check and remove old pairs
if position > 0 and colors[position] != 0 and colors[position - 1] == colors[position]:
    adjacent_same_color_count -= 1

# ... other checks ...

# Update color AFTER all calculations
colors[position] = new_color

2. Forgetting to Check for Zero (Uncolored) Values

Another critical mistake is not properly handling uncolored elements (value 0). Uncolored elements should never contribute to the matching pair count, even if two adjacent elements are both 0.

Incorrect approach:

# WRONG: Not checking if color is 0
if position > 0 and colors[position - 1] == new_color:
    adjacent_same_color_count += 1  # This would count pairs of zeros!

Correct approach:

# RIGHT: Ensure we're not counting zero-colored pairs
if position > 0 and colors[position - 1] == new_color and new_color != 0:
    adjacent_same_color_count += 1

3. Double Counting or Missing Pairs When a Position is Recolored

When a position that already has a color is being recolored with the same color, you need to be careful not to double-count existing pairs or incorrectly remove pairs that should remain.

Example scenario: If position i has color 2, and both neighbors also have color 2, recoloring position i with color 2 again shouldn't change the count. The implementation handles this correctly by first removing the existing pairs (subtracting 2) and then adding them back (adding 2), resulting in no net change.

4. Incorrect Boundary Checking

Failing to properly check array boundaries can lead to index out of bounds errors or incorrect counts at the edges of the array.

Incorrect approach:

# WRONG: Not checking boundaries
if colors[position - 1] == colors[position]:  # Could fail when position = 0
    adjacent_same_color_count -= 1

Correct approach:

# RIGHT: Always check boundaries first
if position > 0 and colors[position - 1] == colors[position]:
    adjacent_same_color_count -= 1