Skip to main content
Talentd

Number of Adjacent Elements With the Same Color - Solution & Explanation

MediumArray17 min readAsked at: Amazon, Meta, Capital One +4
Practice this problem

Problem Statement

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:

  • Set colors[indexi] to colori.
  • Count adjacent pairs in 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:

  • Initially array colors = [0,0,0,0], where 0 denotes uncolored elements of the array.
  • After the 1st query colors = [2,0,0,0]. The count of adjacent pairs with the same color is 0.
  • After the 2nd query colors = [2,2,0,0]. The count of adjacent pairs with the same color is 1.
  • After the 3rd query colors = [2,2,0,1]. The count of adjacent pairs with the same color is 1.
  • After the 4th query colors = [2,1,0,1]. The count of adjacent pairs with the same color is 0.
  • After the 5th query colors = [2,1,1,1]. The count of adjacent pairs with the same color is 2.

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 <= 105
  • 1 <= queries.length <= 105
  • queries[i].length == 2
  • 0 <= indexi <= n - 1
  • 1 <=  colori <= 105

Approach Overview

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.

Approach 1: Approach 1: Direct Updating with Adjacent Check

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(queriesSize) because we process each query individually.

Space Complexity: O(n) for the color array and result array.

Try this approach in the editor →

Approach 2: Approach 2: Optimized Verification with Lazy Initialization

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(queriesSize) since each query is still processed separately.

Space Complexity: O(n) for storing the initial colors array.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Direct Updating with Adjacent Check

Time Complexity: O(queriesSize) because we process each query individually.

Space Complexity: O(n) for the color array and result array.

Approach 2: Optimized Verification with Lazy Initialization

Time Complexity: O(queriesSize) since each query is still processed separately.

Space Complexity: O(n) for storing the initial colors array.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct Updating with Adjacent CheckO(q)O(n)Best general solution. Maintain a running count and update only affected neighbors.
Optimized Verification with Lazy InitializationO(q)O(n)Useful when you want clearer handling of uncolored indices using sentinel values.

Video Solution

Number of Adjacent Elements With the Same Color - Leetcode 2672 - Python • Algorithms Casts • 1,399 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Number of Adjacent Elements With the Same Color easy or hard?
The problem is rated Medium because the implementation requires careful handling of updates and edge cases such as recoloring an already colored index. The core logic is simple once you realize only adjacent neighbors can affect the answer after each query.
Number of Adjacent Elements With the Same Color Python/Java solution
Implementations in Python or Java follow the same idea: store colors in an array, keep a running adjacency counter, and update neighbor relationships on every query. Each query checks indices i-1 and i+1 before and after recoloring. This produces an O(q) time solution with O(n) space.
How to solve Number of Adjacent Elements With the Same Color in O(n)?
Maintain an array of colors and a variable storing the number of adjacent equal pairs. For each query, subtract matches formed by the old color with neighbors, update the color, then check neighbors again to add new matches. Because only two pairs can change per update, each query takes O(1) time.
What is the best approach for Number of Adjacent Elements With the Same Color?
The best approach keeps a running count of adjacent equal pairs and updates it locally after each query. When recoloring index i, check only neighbors i-1 and i+1. Remove previous matches involving the old color, assign the new color, then add new matches. This runs in O(q) time for q queries with O(n) space.
Is Number of Adjacent Elements With the Same Color asked at Google/Amazon/Meta?
Problems with incremental array updates and adjacency tracking appear frequently in interviews at large tech companies. Variants of this pattern—maintaining counts while processing updates—have been reported in interviews at companies like Amazon and Google because they test state management and edge-case handling.
What data structure is used in Number of Adjacent Elements With the Same Color?
The primary data structure is a simple array storing the current color of each index. The algorithm also maintains a single integer counter tracking adjacent equal pairs. No complex structures are required because each update affects only neighboring elements.
What is the time complexity of Number of Adjacent Elements With the Same Color?
The optimal solution runs in O(q) time where q is the number of queries. Each query performs constant work by checking at most two neighbors and updating a counter. Space complexity is O(n) to store the current color of each array position.

Ready to solve this problem?

Practice Number of Adjacent Elements With the Same Color with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays