Number of Adjacent Elements With the Same Color

Number of Adjacent Elements With the Same Color

What is this problem about?

The Number of Adjacent Elements With the Same Color problem gives you an array (initially all uncolored), a number of colors, and a sequence of color assignments. After each assignment, report how many adjacent pairs have the same color. This coding problem maintains a running count efficiently rather than recomputing from scratch after each update.

Why is this asked in interviews?

Uber, Visa, Roblox, Amazon, TikTok, and Capital One ask this to test efficient count maintenance under array updates. The naive O(n) recount per query is too slow — the O(1) per update solution requires tracking which adjacent pairs are affected by each assignment. The array interview pattern is demonstrated with incremental update reasoning.

Algorithmic pattern used

Incremental update with neighbor check. Maintain a running count of same-color adjacent pairs. For each assignment (index, color): before assigning, subtract the contribution of the current element's existing adjacent matches (check left neighbor and right neighbor). After assigning the new color, add the new adjacent matches. This updates count in O(1) per query.

Example explanation

Array (0-indexed): initially [0,0,0,0] (0=uncolored). count=0.

• Assign index=1, color=2: old value=0. Left neighbor (0): 0≠2, right (2): 0≠2. No subtraction. After: arr=[0,2,0,0]. New matches: none added. count=0.
• Assign index=2, color=2: old value=0. After: arr=[0,2,2,0]. Left (2): 2==2 → count++. Right (0): 0≠2. count=1.
• Assign index=1, color=1: old value=2. Left (0): 0≠2, right (2): 2==2 → subtract 1. count=0. New arr=[0,1,2,0]. Left (0)≠1, right (2)≠1. count stays 0.

Common mistakes candidates make

• Recomputing the full array after each update (O(n) per query).
• Forgetting to subtract old matches before updating, then add new matches.
• Not checking both left and right neighbors for both subtract and add phases.
• Boundary errors at index 0 and n-1 (only one neighbor).

Interview preparation tip

Incremental update problems require identifying what changes locally around each modification. For adjacency problems: only the left-pair and right-pair of the modified element can change. Calculate the "before" contribution, apply the update, calculate the "after" contribution, and adjust the running count accordingly. This O(1)-per-update pattern generalizes to any array query where modifications have bounded local effects — practice it with "count of equal pairs" and "count inversions under updates."