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.

Description Hints 3 Solution Video 12:00

2672. Number of Adjacent Elements With the Same Color

Medium59.8% acceptance7 companies

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] = [index_i, color_i]. For the i^th query:

Set colors[index_i] to color_i.
Count adjacent pairs in colors set to the same color (regardless of color_i).

Return an array answer of the same length as queries where answer[i] is the answer to the i^th 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 1^st query colors = [2,0,0,0]. The count of adjacent pairs with the same color is 0.
After the 2^nd query colors = [2,2,0,0]. The count of adjacent pairs with the same color is 1.
After the 3^rd query colors = [2,2,0,1]. The count of adjacent pairs with the same color is 1.
After the 4^th query colors = [2,1,0,1]. The count of adjacent pairs with the same color is 0.
After the 5^th 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 1^st query colors = [100000]. The count of adjacent pairs with the same color is 0.

Constraints:

1 <= n <= 10⁵
1 <= queries.length <= 10⁵
queries[i].length == 2
0 <= index_i <= n - 1
1 <= color_i <= 10⁵

Asked at 7 companies

Capital One Visa Roblox Uber Tiktok Amazon Meta

Topics

Array

Hints open one at a time

Hint 1

Since at each query, only one element is being recolored, we just need to focus on its neighbors.

Hint 2

If an element that is changed on the i-th query had the same color as its right element answer decreases by 1. Similarly contributes its left element too.

Hint 3

After changing the color, if the element has the same color as its right element answer increases by 1. Similarly contributes its left element too.

12:00

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

4
[[0,2],[1,2],[3,1],[1,1],[2,1]]

Input

1
[[0,100000]]

Your code is saved on this device.Solution