Number of Adjacent Elements With the Same Color

LeetCode 2672. Number of Adjacent Elements With the Same Color gives you an array of length n where every cell starts uncolored (value 0). You receive a list of queries, each one setting a specific index to a color. After each query, you need to report how many adjacent pairs share the same non-zero color.

The brute force approach

The most obvious solution: after each query, walk the entire array and count adjacent matching pairs.

def color_the_array(n, queries):
    colors = [0] * n
    result = []
    for idx, color in queries:
        colors[idx] = color
        count = 0
        for i in range(n - 1):
            if colors[i] != 0 and colors[i] == colors[i + 1]:
                count += 1
        result.append(count)
    return result

This works, but each query triggers a full scan of the array. If n and the number of queries q are both up to 10^5, you are looking at O(n * q) total work. That is up to 10^10 operations, which is far too slow.

The key insight: maintain a running count

Think about what happens when you change one cell. Only the pairs involving that cell can be affected. Cell i has at most two neighbors: i-1 and i+1. So the count can change by at most 2 in either direction.

The approach:

1. Before changing colors[i], check if the old value matched the left neighbor or the right neighbor. Subtract those matches from the count.
2. Set colors[i] to the new color.
3. After the change, check if the new value matches the left or right neighbor. Add those matches to the count.

Each query does a constant number of comparisons. No scanning.

def color_the_array(n, queries):
    colors = [0] * n
    count = 0
    result = []
    for idx, color in queries:
        old = colors[idx]
        if old != 0:
            if idx > 0 and colors[idx - 1] == old:
                count -= 1
            if idx < n - 1 and colors[idx + 1] == old:
                count -= 1
        colors[idx] = color
        if color != 0:
            if idx > 0 and colors[idx - 1] == color:
                count += 1
            if idx < n - 1 and colors[idx + 1] == color:
                count += 1
        result.append(count)
    return result

That is the entire solution. No extra data structures, no complicated logic. Just careful bookkeeping around one cell at a time.

Visual walkthrough

Let's trace through the full example: n = 4, queries = [[0,2],[1,2],[3,1],[1,1],[2,1]].

The expected output is [0, 1, 1, 0, 2].

Notice how the count only changes when a neighbor relationship is created or broken. In step 4, changing cell 1 from color 2 to color 1 breaks its match with cell 0 (still color 2) without creating any new matches. In step 5, coloring cell 2 creates two new matches at once because both neighbors happen to share the same color.

Why we skip uncolored cells

The problem states that matching pairs must share the same non-zero color. Two uncolored cells sitting next to each other do not count. That is why the code checks if old != 0 before subtracting and if color != 0 before adding. Without these guards, you would incorrectly count pairs of zeros as matches.

Complexity analysis

Compare this to the brute force O(n * q). For n = q = 100,000, that is the difference between 400,000 operations and 10,000,000,000 operations.

The building block: incremental state maintenance

The core technique here is not specific to colors or arrays. It is a general pattern: when a small change happens, update the answer incrementally instead of recomputing from scratch.

You see this same idea in many problems:

• Sliding window problems: when the window moves one step, you add the new element and remove the old one instead of recalculating the entire window.
• Union-Find (DSU): when you merge two sets, you update the component count by 1 instead of recounting all components.
• Dynamic connectivity: when an edge is added or removed, update the affected count rather than running a full traversal.

The pattern is always the same. You ask: "What is the maximum amount the answer can change from this one operation?" If the answer is bounded by a constant, you can maintain it incrementally.

Edge cases

n = 1: A single-element array has no adjacent pairs. The count is always 0 regardless of queries.

Coloring the same index multiple times: This is exactly why the "subtract before, add after" pattern matters. You must undo the old color's contribution before applying the new one. Forgetting the subtraction step is the most common bug.

All cells the same color: If every cell ends up with color c, the count is n - 1. The incremental approach handles this naturally, adding one match at a time as each cell gets colored.

From understanding to recall

Reading through this solution, the logic feels clean and simple. But try closing this page and writing it from scratch in five minutes. The tricky part is not the algorithm itself. It is remembering the exact order of operations: subtract old matches first, then update the cell, then add new matches. Swap any two of those steps and you get wrong answers.

This is exactly the kind of problem where spaced repetition shines. The building block (incremental count maintenance with subtract-before, add-after) is small enough to drill in under a minute. After a few review cycles at increasing intervals, the pattern sticks permanently. When you see a similar problem in an interview, you will not need to rederive it.

Related posts

• Contains Duplicate - Another array problem where the right data structure turns an O(n^2) brute force into a linear solution.
• Longest Consecutive Sequence - Uses incremental set-based reasoning to solve what looks like a sorting problem in O(n) time.