Number of Adjacent Elements With the Same Color
Asked at Capital One
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Capital One | Medium | View all Capital One questions → |
How to Think About It
Recounting all pairs after each query is O(n) per query — O(n * q) overall.
Key insight: changing colors[i] can only change the status of the pairs (i-1, i) and (i, i+1). Everything else is untouched.
Before recoloring, subtract any of those pairs that currently match (with a non-zero color). After recoloring, add any that match now.
Uncolored cells (0) never count as matching.
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).
What Trips People Up in Real Interviews
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.
Solution Code
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 resFrequently 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.