#2672

Medium

auto_awesomeArray-driven solution strategy

LeetCode Problem Workspace

Number of Adjacent Elements With the Same Color

Calculate the number of adjacent elements sharing the same color after sequentially updating an initially zeroed array using queries.

array

Problem Statement

You are given an integer n representing the length of an initially uncolored array colors, where all elements are set to 0. You are also provided a 2D integer array queries where each query consists of [indexi, colori], indicating that colors[indexi] should be updated to colori sequentially.

Return an array answer of the same length as queries where answer[i] is the number of adjacent element pairs in colors that have the same color immediately after performing the ith query. For example, for n = 4 and queries = [[0,2],[1,2],[3,1],[1,1],[2,1]], the correct output is [0,1,1,0,2].

Examples

Example 1

Input: n = 4, queries = [[0,2],[1,2],[3,1],[1,1],[2,1]]

Output: [0,1,1,0,2]

Example 2

Input: n = 1, queries = [[0,100000]]

Output: [0]

After the 1 st 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

Solution Approach

Track Colors and Neighbors

Maintain the colors array and a counter for adjacent same-color pairs. For each query, check only the element at indexi and its immediate neighbors to update the counter efficiently.

Update Counts Incrementally

Before changing colors[indexi], subtract any existing matching pairs with its neighbors. Apply the new color, then add new matching pairs with neighbors. This ensures each query updates in O(1) time.

Return Results Sequentially

After processing each query and updating the counter, append the current adjacent same-color count to the answer array. Repeat for all queries to form the final output.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(queries.length) because each query only examines up to two neighbors. Space complexity is O(n) for storing the colors array and the answer array.

What Interviewers Usually Probe

Focus on updating only affected neighbors rather than recomputing the entire array.
Expect O(1) updates per query using the array-driven strategy.
Clarify handling of boundary indices to avoid out-of-bounds errors.

Common Pitfalls or Variants

Common pitfalls

Forgetting to subtract previous matching pairs before recoloring an element.
Accessing neighbors without checking array bounds at edges.
Assuming recoloring an element affects distant pairs instead of just immediate neighbors.

Follow-up variants

Count adjacent elements with the same color after batch updates rather than sequential queries.
Support multiple colors and track maximum repeated adjacent color streaks.
Allow queries that recolor ranges of indices instead of a single element.

FAQ

What is the best approach for Number of Adjacent Elements With the Same Color?

Use an array-driven solution tracking the current colors and adjusting the adjacent count only for neighbors of the updated element.

How do I handle the first and last element in the array?

Check neighbors carefully and only consider existing neighbors to avoid out-of-bounds errors.

Can this approach handle large n and many queries efficiently?

Yes, because each query only inspects two neighbors, making the time complexity O(queries.length).

Why is recomputing the entire array after each query inefficient?

Recomputing checks all pairs each time, leading to O(n * queries.length) time instead of O(queries.length).

Does this problem require extra space for neighbors?

No, only the colors array and the answer array are needed; neighbor checks are done in place.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:
        nums = [0] * n
        ans = [0] * len(queries)
        x = 0
        for k, (i, c) in enumerate(queries):
            if i > 0 and nums[i] and nums[i - 1] == nums[i]:
                x -= 1
            if i < n - 1 and nums[i] and nums[i + 1] == nums[i]:
                x -= 1
            if i > 0 and nums[i - 1] == c:
                x += 1
            if i < n - 1 and nums[i + 1] == c:
                x += 1
            ans[k] = x
            nums[i] = c
        return ans

Continue Practicing

#2673 make costs of paths equal in a binary tree #2670 find the distinct difference array #2678 number of senior citizens