Number of Adjacent Elements With the Same Color - Video Solutions

Problem Overview: You maintain an array of size n where every element starts uncolored. Each query assigns a color to an index. After every update, return how many adjacent pairs (i, i+1) currently share the same color.

The key observation: only the neighbors of the updated index can change the number of valid adjacent pairs. You never need to recompute the entire array after each query.

Approach 1: Direct Updating with Adjacent Check (Time: O(q), Space: O(n))

Maintain an array storing the current color at each index and a running counter for adjacent equal pairs. For every query (idx, color), first check if the index already had a color. If so, remove any existing contributions with neighbors idx-1 and idx+1 where the colors matched. Then update the color at idx and re-check the same neighbors to add back any new matches. Each query performs constant work: two neighbor comparisons and a few counter updates. This makes the total time O(q) for q queries, with O(n) space for the color array. This approach is essentially a small array simulation where updates affect only local state.

Approach 2: Optimized Verification with Lazy Initialization (Time: O(q), Space: O(n))

Instead of initializing the entire array with a default color, store a sentinel value such as -1 to represent an uncolored position and treat it as invalid during comparisons. When processing a query, skip neighbor checks if the neighbor is still uncolored. This avoids unnecessary comparisons early in the process and keeps the logic explicit: only colored cells participate in adjacency counts. The algorithm still performs constant work per query, so the time complexity remains O(q) with O(n) space. Conceptually this is the same incremental update strategy but with cleaner handling of uninitialized cells.

Both approaches rely on the same insight: recomputing the entire array after each update would be O(nq), which is unnecessary. Only two potential adjacent pairs can change when a single index is recolored.

Recommended for interviews: Approach 1 is what interviewers expect. It demonstrates that you recognize the local impact of an update and maintain a running count instead of recomputing from scratch. Explaining why only idx-1 and idx+1 matter shows strong understanding of array state updates and incremental simulation. The lazy initialization variation is a small optimization but the core idea—subtract old matches, update, then add new matches—is the important part.