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.

#2672

Medium

auto_awesome数组·driven

LeetCode 题解工作台

有相同颜色的相邻元素数目

给定一个整数 n 表示一个长度为 n 的数组 colors ，初始所有元素均为 0 ，表示是未染色的。同时给定一个二维整数数组 queries ，其中 queries[i] = [index i , color i ] 。对于第 i 个查询：将 colors[index i ] 染色为 c…

数组

题目描述

给定一个整数 n 表示一个长度为 n 的数组 colors，初始所有元素均为 0 ，表示是 未染色 的。同时给定一个二维整数数组 queries，其中 queries[i] = [index_i, color_i]。对于第 i 个查询：

将 colors[index_i] 染色为 color_i。
统计 colors 中颜色相同的相邻对的数量（无论 color_i）。

请你返回一个长度与 queries 相等的数组 answer ，其中 answer[i]是前 i 个操作的答案。

示例 1：

输入：n = 4, queries = [[0,2],[1,2],[3,1],[1,1],[2,1]]

输出：[0,1,1,0,2]

解释：

一开始 colors = [0,0,0,0]，其中 0 表示数组中未染色的元素。
在第 1 次查询后 colors = [2,0,0,0]。颜色相同的相邻对的数量是 0。
在第 2 次查询后 colors = [2,2,0,0]。颜色相同的相邻对的数量是 1。
在第 3 次查询后 colors = [2,2,0,1]。颜色相同的相邻对的数量是 1。
在第 4 次查询后 colors = [2,1,0,1]。颜色相同的相邻对的数量是 0。
在第 5 次查询后 colors = [2,1,1,1]。颜色相同的相邻对的数量是 2。

示例 2：

输入：n = 1, queries = [[0,100000]]

输出：[0]

解释：

在第一次查询后 colors = [100000]。颜色相同的相邻对的数量是 0。

提示：

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

lightbulb

解题思路

方法一

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

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

speed

复杂度分析

指标	值
时间	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.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#2673 使二叉树所有路径值相等的最小代价 #2670 找出不同元素数目差数组 #2678 老人的数目