2672. Number of Adjacent Elements With the Same Color
Medium58.1% acceptance29,674 / 51,064 submissions
Asked by 6 companies
Topics
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]tocolori. - Count the number of adjacent pairs in
colorswhich have the same color (regardless ofcolori).
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 <= 1051 <= queries.length <= 105queries[i].length == 20 <= indexi <= n - 11 <= colori <= 105
Hints
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.