You are given an integer n representing an array colors of length n where all elements are set to 0's meaning uncolored. You are also given a 2D integer array queries where queries[i] = [indexi, colori]. For the ith query:
colors[indexi] to colori.colors set to the same color (regardless of colori).Return an array answer of the same length as queries where answer[i] is the answer to the ith query.
Example 1:
Input: n = 4, queries = [[0,2],[1,2],[3,1],[1,1],[2,1]]
Output: [0,1,1,0,2]
Explanation:
Example 2:
Input: n = 1, queries = [[0,100000]]
Output: [0]
Explanation:
After the 1st query colors = [100000]. The count of adjacent pairs with the same color is 0.
Constraints:
1 <= n <= 1051 <= queries.length <= 105queries[i].length == 20 <= indexi <= n - 11 <= colori <= 105Problem 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.
We iterate through each query, updating the color of the given index in the colors array. After each update, we check the color of the neighboring elements (left and right) to determine if there is an increase or decrease in the count of adjacent similar colors. This direct checking ensures we update our result efficiently.
The solution involves tracking the number of adjacent elements with the same color by iterating over the queries one at a time. For each query, we update the element at the specified index and adjust the count of similar adjacent pairs by checking both the left and right neighbors before and after the update.
Time Complexity: O(queriesSize) because we process each query individually.
Space Complexity: O(n) for the color array and result array.
This approach optimizes the process by using lazy initialization. Instead of resetting counts each time, it uses previous state data. Before updating an element, adjacent pairs are compared, and only necessary changes are tracked and updated in the adjacent count.
A more optimized way to manage color changes is implemented in this C solution by minimizing recalculations. Instead of recalculating entirely, only changes around the updated index are considered, thus saving computational resources.
Time Complexity: O(queriesSize) since each query is still processed separately.
Space Complexity: O(n) for storing the initial colors array.
| Approach | Complexity |
|---|---|
| Approach 1: Direct Updating with Adjacent Check | Time Complexity: Space Complexity: |
| Approach 2: Optimized Verification with Lazy Initialization | Time Complexity: Space Complexity: |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Updating with Adjacent Check | O(q) | O(n) | Best general solution. Maintain a running count and update only affected neighbors. |
| Optimized Verification with Lazy Initialization | O(q) | O(n) | Useful when you want clearer handling of uncolored indices using sentinel values. |
How to EASILY solve LeetCode problems • NeetCode • 427,736 views views
Watch 9 more video solutions →Practice Number of Adjacent Elements With the Same Color with our built-in code editor and test cases.
Practice on FleetCode