MediumArrayUpdated Sep 2026

2672. Number of Adjacent Elements With the Same Color

Asked at Capital One

Difficulty

Medium

Time

O(n + q)

Space

O(n)

Pattern

Array

Companies

1

Problem

You have an array colors of length n. At the start every cell is 0, which means uncolored. You also get a list of queries, where each query is a pair [index, color].

Process the queries in order. For each query, paint the cell at index with color, then report how many adjacent pairs in the whole array currently have the same color. A pair is two cells that sit next to each other, like positions i and i+1. Uncolored cells (value 0) never match anything, not even another 0.

Return an array of the same length as queries. Entry i is the pair count right after query i is applied. Note that painting a cell can also break an existing match, so the count can go down.

Paint one cell, recount matching neighbors

colors00000123Start: every cell is uncolored (0), so there are nomatching pairs.colorsmatch22000123After painting index 1 with color 2, pair (0,1)matches → count 1.colors21010123Repainting index 1 with color 1 breaks pair (0,1) →count drops back to 0.
Each query changes one cell, and only the pairs touching that cell can change.

Constraints

  • ●1 <= n <= 10^5
  • ●1 <= queries.length <= 10^5
  • ●queries[i].length == 2
  • ●0 <= index_i <= n - 1
  • ●1 <= color_i <= 10^5

Examples

Example 1
Inputn = 4, queries = [[0,2],[1,2],[3,1],[1,1],[2,1]]
Output[0,1,1,0,2]
WhyStart: [0,0,0,0]. Paint index 0 with 2 → [2,0,0,0], no matching neighbors, so 0. Paint index 1 with 2 → [2,2,0,0], pair (0,1) matches, so 1. Paint index 3 with 1 → [2,2,0,1], still only pair (0,1), so 1. Repaint index 1 with 1 → [2,1,0,1], pair (0,1) no longer matches, so 0. Paint index 2 with 1 → [
Example 2
Inputn = 1, queries = [[0,100000]]
Output[0]
WhyWith only one cell there is no neighbor to pair with, so the count is always 0.

Asked At

1 companies
CompanyDifficulty
Capital OneMediumView all Capital One questions →

How to Think About It

1

Recounting all pairs after each query is O(n) per query — O(n * q) overall.

2

Key insight: changing colors[i] can only change the status of the pairs (i-1, i) and (i, i+1). Everything else is untouched.

3

Before recoloring, subtract any of those pairs that currently match (with a non-zero color). After recoloring, add any that match now.

4

Uncolored cells (0) never count as matching.

5

Walkthrough: n = 4: color 0 red -> 0 pairs; color 1 red -> pair (0,1) -> 1; color 3 blue -> 1; color 1 blue -> pair (0,1) lost -> 0; color 2 blue -> pairs (1,2), (2,3) -> 2.

Optimal Approach

Step 1: colors = [0] * n, count = 0.
Step 2: For each query (i, c):
For each neighbor j in {i-1, i+1} within bounds: if colors[i] != 0 and colors[i] == colors[j], count -= 1.
colors[i] = c.
For each neighbor j: if colors[j] == c, count += 1.
Record count.
Step 3: Return the recorded counts.

Time: O(n + q). Space: O(n).

Only two pairs can change

subtract matches at (i-1,i) and (i,i+1)colors[i] = cadd matches at (i-1,i) and (i,i+1)append count to answerFour small steps per query, each looking at at mosttwo neighbors.colors21010123iQuery (1,1): before repaint, check neighbors 0 and 2for matches with the old value.colorsmatchmatch21110123After repainting index 1, both neighbor pairs match →count 2.count -= old matchescount += new matchesanswer[i] = count
Remove old matches around the cell, repaint, then add new matches around it.
ComplexityTime O(n + q)Space O(n)We build the array once and each query touches only two neighbor pairs, so the total work is linear in n plus the number of queries.

What Trips People Up in Real Interviews

1

Counting two uncolored neighbors as a matching pair.

2

Recoloring an index with its current color: subtract-then-add handles it correctly, but skipping the subtraction double-counts.

3

Recounting the whole array after each query.

4

Index errors at the array ends.

Solution Code

O(n + q) time
def colorTheArray(n, queries):
    colors = [0] * n
    count = 0
    res = []
    for i, c in queries:
        for j in (i - 1, i + 1):
            if 0 <= j < n and colors[i] != 0 and colors[i] == colors[j]:
                count -= 1
        colors[i] = c
        for j in (i - 1, i + 1):
            if 0 <= j < n and colors[j] == c:
                count += 1
        res.append(count)
    return res

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Number of Adjacent Elements With the Same Color problem?

Number of Adjacent Elements With the Same Color starts with an uncolored array and applies queries that color index `i` with color `c`. After each query, report how many adjacent pairs share the same (non-zero) color. Recounting the whole array per query is too slow; each query only affects the two pairs touching the changed index.

How do you solve Number of Adjacent Elements With the Same Color?

The optimal approach runs in O(n + q) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Number of Adjacent Elements With the Same Color?

Number of Adjacent Elements With the Same Color is asked at Capital One. It is a medium difficulty problem.

What are common mistakes on Number of Adjacent Elements With the Same Color?
  • Counting two uncolored neighbors as a matching pair.
  • Recoloring an index with its current color: subtract-then-add handles it correctly, but skipping the subtraction double-counts.
  • Recounting the whole array after each query.
  • Index errors at the array ends.