LeetCode 2672 - Number of Adjacent Elements With the Same Color

LeetCode Problem 2672

Difficulty: 🟡 Medium
Topics: Array

Solution

Problem Understanding

The problem gives us an array called colors of length n. Initially, every element is 0, which represents an uncolored position.

We then process a sequence of queries. Each query contains two integers:

• indexi, the position we want to update
• colori, the new color assigned to that position

After applying each query, we must determine how many adjacent pairs in the array have the same nonzero color.

An adjacent pair means two neighboring indices:

• (0, 1)
• (1, 2)
• (2, 3)
• and so on

For example, if the array becomes:

[2, 2, 1, 1]

then there are two valid adjacent equal-color pairs:

• (0, 1) because 2 == 2
• (2, 3) because 1 == 1

So the answer would be 2.

A key detail is that colors can be overwritten. A position may already contain a color and later receive a different one. Every query modifies the current state of the array.

The constraints are important:

• n <= 100000
• queries.length <= 100000

This means we must handle up to one hundred thousand updates efficiently. Any solution that scans the entire array after every query would be too slow.

The input guarantees:

• indices are always valid
• colors are positive integers
• only 0 represents "uncolored"

Several edge cases are important:

• Arrays of length 1, where no adjacent pairs can ever exist
• Recoloring a position with the same color it already has
• Breaking an existing adjacent pair when changing a color
• Creating one or two new adjacent pairs after an update
• Updates at the boundaries of the array, where only one neighbor exists

These edge cases are exactly where incorrect counting logic usually appears.

Approaches

Brute Force Approach

The most direct solution is to simulate every query and recompute the number of adjacent equal-color pairs from scratch.

After applying a query:

1. Update colors[index]
2. Iterate through the entire array
3. Count how many adjacent positions satisfy:

• colors[i] != 0
• colors[i] == colors[i + 1]

This approach is correct because it explicitly checks every adjacent pair after every update.

However, it is too slow.

If there are q queries, and each query scans all n elements, the complexity becomes:

O(n * q)

With both values potentially equal to 100000, this could require up to 10^10 operations, which is far beyond acceptable limits.

Optimal Approach

The key observation is that changing one index only affects adjacent pairs involving that index.

When we update position i, only these pairs can change:

• (i - 1, i)
• (i, i + 1)

No other adjacent pair is affected.

This means we do not need to recompute the entire array after each query. Instead, we maintain a running count of valid adjacent equal-color pairs.

For every update:

1. Remove contributions from the old color relationships
2. Change the color
3. Add contributions from the new color relationships

Since each query only checks at most two neighbors, every query runs in constant time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × q)	O(n)	Recomputes all adjacent pairs after every query
Optimal	O(q)	O(n)	Only updates affected neighboring pairs

Algorithm Walkthrough

Step 1: Initialize the colors array

Create an array colors of length n filled with 0.

colors = [0] * n

This represents the initial uncolored state.

We also maintain:

adjacent_pairs = 0

This variable stores the current number of valid adjacent equal-color pairs.

Step 2: Process each query

For every query [index, new_color], we update the array and adjust the count.

Step 3: Remove old pair contributions

Before changing the color at index, we must remove any adjacent equal-color pairs currently involving that position.

We check the left neighbor:

if index > 0 and colors[index] != 0 and colors[index] == colors[index - 1]:

If true, decrement the count.

Then check the right neighbor:

if index < n - 1 and colors[index] != 0 and colors[index] == colors[index + 1]:

If true, decrement again.

We do this first because the old color is about to disappear.

Step 4: Apply the new color

Update the array:

colors[index] = new_color

Step 5: Add new pair contributions

Now check whether the new color forms equal adjacent pairs with neighbors.

Check left neighbor:

if index > 0 and colors[index] == colors[index - 1]:

If true, increment the count.

Check right neighbor:

if index < n - 1 and colors[index] == colors[index + 1]:

If true, increment again.

Step 6: Store the current answer

Append the current value of adjacent_pairs to the result array.

Why it works

The algorithm works because only adjacent pairs touching the updated index can change after a query.

Every query modifies exactly one position. Therefore:

• all unrelated adjacent pairs remain unchanged
• only (i - 1, i) and (i, i + 1) may be created or destroyed

By removing old contributions before the update and adding new contributions afterward, the running count always remains accurate.

This invariant guarantees correctness after every query.

Python Solution

from typing import List

class Solution:
    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:
        colors = [0] * n
        adjacent_pairs = 0
        answer = []

        for index, new_color in queries:
            current_color = colors[index]

            # Remove old contributions
            if current_color != 0:
                if index > 0 and colors[index - 1] == current_color:
                    adjacent_pairs -= 1

                if index < n - 1 and colors[index + 1] == current_color:
                    adjacent_pairs -= 1

            # Apply update
            colors[index] = new_color

            # Add new contributions
            if index > 0 and colors[index - 1] == new_color:
                adjacent_pairs += 1

            if index < n - 1 and colors[index + 1] == new_color:
                adjacent_pairs += 1

            answer.append(adjacent_pairs)

        return answer

The implementation follows the algorithm directly.

The colors array stores the current state after every query. The variable adjacent_pairs maintains the running count of valid adjacent equal-color pairs.

Before updating a position, the code removes any existing pair contributions involving the current color at that index. This prevents stale pairs from remaining in the count after recoloring.

After assigning the new color, the code checks whether the updated position now forms equal-color pairs with its neighbors. Any newly formed pairs are added back into the count.

Each query touches at most two neighbors, which keeps the runtime constant per operation.

Go Solution

func colorTheArray(n int, queries [][]int) []int {
    colors := make([]int, n)
    adjacentPairs := 0
    answer := make([]int, 0, len(queries))

    for _, query := range queries {
        index := query[0]
        newColor := query[1]

        currentColor := colors[index]

        // Remove old contributions
        if currentColor != 0 {
            if index > 0 && colors[index-1] == currentColor {
                adjacentPairs--
            }

            if index < n-1 && colors[index+1] == currentColor {
                adjacentPairs--
            }
        }

        // Apply update
        colors[index] = newColor

        // Add new contributions
        if index > 0 && colors[index-1] == newColor {
            adjacentPairs++
        }

        if index < n-1 && colors[index+1] == newColor {
            adjacentPairs++
        }

        answer = append(answer, adjacentPairs)
    }

    return answer
}

The Go implementation mirrors the Python logic closely.

Slices are used instead of dynamic Python lists. The answer slice is initialized with capacity equal to the number of queries to reduce reallocations.

Go integers are sufficient because the maximum number of adjacent pairs is at most n - 1, which easily fits inside a standard int.

No special handling for nil values is required because the array is initialized with zeros automatically.

Worked Examples

Example 1

Input:

n = 4
queries = [[0,2],[1,2],[3,1],[1,1],[2,1]]

Initial state:

colors = [0,0,0,0]
adjacent_pairs = 0

Query	Colors After Update	Adjacent Pairs	Explanation
[0,2]	[2,0,0,0]	0	No equal neighbors
[1,2]	[2,2,0,0]	1	Pair (0,1) created
[3,1]	[2,2,0,1]	1	No new equal pairs
[1,1]	[2,1,0,1]	0	Pair (0,1) removed
[2,1]	[2,1,1,1]	2	Pairs (1,2) and (2,3) created

Final answer:

[0,1,1,0,2]

Example 2

Input:

n = 1
queries = [[0,100000]]

Initial state:

colors = [0]
adjacent_pairs = 0

Query	Colors After Update	Adjacent Pairs	Explanation
[0,100000]	[100000]	0	No neighbors exist

Final answer:

[0]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(q)	Each query checks at most two neighbors
Space	O(n)	The colors array stores the current state

The algorithm processes each query in constant time because only neighboring pairs around the updated index can change.

The extra space comes from storing the current color of every position in the array.

Test Cases

from typing import List

class Solution:
    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:
        colors = [0] * n
        adjacent_pairs = 0
        answer = []

        for index, new_color in queries:
            current_color = colors[index]

            if current_color != 0:
                if index > 0 and colors[index - 1] == current_color:
                    adjacent_pairs -= 1

                if index < n - 1 and colors[index + 1] == current_color:
                    adjacent_pairs -= 1

            colors[index] = new_color

            if index > 0 and colors[index - 1] == new_color:
                adjacent_pairs += 1

            if index < n - 1 and colors[index + 1] == new_color:
                adjacent_pairs += 1

            answer.append(adjacent_pairs)

        return answer

solution = Solution()

# Provided example 1
assert solution.colorTheArray(
    4,
    [[0,2],[1,2],[3,1],[1,1],[2,1]]
) == [0,1,1,0,2]

# Provided example 2
assert solution.colorTheArray(
    1,
    [[0,100000]]
) == [0]

# No adjacent matches ever formed
assert solution.colorTheArray(
    5,
    [[0,1],[2,2],[4,3]]
) == [0,0,0]

# Creating multiple adjacent pairs
assert solution.colorTheArray(
    5,
    [[1,7],[2,7],[3,7]]
) == [0,1,2]

# Breaking an existing pair
assert solution.colorTheArray(
    3,
    [[0,1],[1,1],[1,2]]
) == [0,1,0]

# Recoloring with the same color
assert solution.colorTheArray(
    3,
    [[0,5],[1,5],[1,5]]
) == [0,1,1]

# Updating boundaries
assert solution.colorTheArray(
    4,
    [[0,1],[3,1],[1,1],[2,1]]
) == [0,0,1,3]

# Single element array with multiple updates
assert solution.colorTheArray(
    1,
    [[0,1],[0,2],[0,3]]
) == [0,0,0]

# Large chain formation
assert solution.colorTheArray(
    6,
    [[0,9],[1,9],[2,9],[3,9],[4,9],[5,9]]
) == [0,1,2,3,4,5]

Test Summary

Test	Why
Example 1	Validates standard mixed updates
Example 2	Validates size 1 array
No adjacent matches	Ensures unrelated colors do not affect count
Multiple adjacent creation	Tests consecutive pair formation
Breaking a pair	Ensures old contributions are removed correctly
Recoloring same value	Tests idempotent updates
Boundary updates	Validates edge index handling
Single element multiple updates	Ensures no invalid neighbor access
Large chain formation	Tests repeated pair accumulation

Edge Cases

Array of Length One

When n = 1, there are no adjacent positions at all. A careless implementation might attempt to access neighbors and cause index errors.

The solution avoids this by checking boundary conditions before accessing neighbors:

if index > 0
if index < n - 1

Because neither condition is true for a single-element array, no neighbor checks occur.

Recoloring a Position With the Same Color

Suppose the array contains:

[5,5]

and we apply another query setting the second position to 5 again.

A buggy implementation could accidentally double count the adjacent pair. This solution first removes existing contributions and then re-adds them after the update, keeping the count unchanged and correct.

Updating a Position That Connects Two Equal Segments

Consider:

[1,0,1]

If we update the middle position to 1, two adjacent pairs are created simultaneously:

[1,1,1]

Now both (0,1) and (1,2) are valid.

The algorithm handles this correctly because it independently checks both neighbors after the update and increments the count for each matching side.