2672

2672. Number of Adjacent Elements With the Same Color (Medium)

There is a 0-indexed array nums of length n. Initially, all elements are uncolored (has a value of 0).

You are given a 2D integer array queries where queries[i] = [indexi, colori].

For each query, you color the index indexi with the color colori in the array nums.

Return an array answer of the same length as queries where answer[i] is the number of adjacent elements with the same color after the ith query.

More formally, answer[i] is the number of indices j, such that 0 <= j < n - 1 and nums[j] == nums[j + 1] and nums[j] != 0 after 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 nums = [0,0,0,0], where 0 denotes uncolored elements of the array.
- After the 1st query nums = [2,0,0,0]. The count of adjacent elements with the same color is 0.
- After the 2nd query nums = [2,2,0,0]. The count of adjacent elements with the same color is 1.
- After the 3rd query nums = [2,2,0,1]. The count of adjacent elements with the same color is 1.
- After the 4th query nums = [2,1,0,1]. The count of adjacent elements with the same color is 0.
- After the 5th query nums = [2,1,1,1]. The count of adjacent elements with the same color is 2.

Example 2:

Input: n = 1, queries = [[0,100000]]
Output: [0]
Explanation: Initially array nums = [0], where 0 denotes uncolored elements of the array.
- After the 1st query nums = [100000]. The count of adjacent elements 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

Related Topics:
Array

Hints:

• Since at each query, only one element is being recolored, we just need to focus on its neighbors.
• 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.
• 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.

Solution 1.

// OJ: https://leetcode.com/problems/number-of-adjacent-elements-with-the-same-color
// Author: github.com/lzl124631x
// Time: O(Q)
// Space: O(N)
class Solution {
public:
    vector<int> colorTheArray(int n, vector<vector<int>>& Q) {
        vector<int> ans;
        int m[100000] = {}, cnt = 0;
        for (auto &q : Q) {
            int i = q[0], c = q[1], prev = m[i];
            if (prev != c) {
                if (prev) {
                    cnt -= i - 1 >= 0 && m[i - 1] == prev;
                    cnt -= i + 1 < n && m[i + 1] == prev;
                }
                m[i] = c;
                cnt += i - 1 >= 0 && m[i - 1] == c;
                cnt += i + 1 < n && m[i + 1] == c;
            }
            ans.push_back(cnt);
        }
        return ans;
    }
};