Skip to content

2672. Number of Adjacent Elements With the Same Color

Description

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] to colori.
  • Count the number of adjacent pairs in colors which have the same color (regardless of colori).

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 <= 105
  • 1 <= queries.length <= 105
  • queries[i].length == 2
  • 0 <= indexi <= n - 1
  • 1 <=  colori <= 105

Solutions

Solution 1

Thinking

Each query recolors one index and must report the number of equal adjacent pairs. Rescanning the array is \(O(nq)\) for \(n,q \le 10^5\). Only the neighbors of the edited index change.

Subtract existing equal pairs with the old color, write the new color, then add pairs that the new color forms. Zeros are uncolored and do not count. A global \(x\) stores the total.

 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int[] colorTheArray(int n, int[][] queries) {
        int m = queries.length;
        int[] nums = new int[n];
        int[] ans = new int[m];
        for (int k = 0, x = 0; k < m; ++k) {
            int i = queries[k][0], c = queries[k][1];
            if (i > 0 && nums[i] > 0 && nums[i - 1] == nums[i]) {
                --x;
            }
            if (i < n - 1 && nums[i] > 0 && nums[i + 1] == nums[i]) {
                --x;
            }
            if (i > 0 && nums[i - 1] == c) {
                ++x;
            }
            if (i < n - 1 && nums[i + 1] == c) {
                ++x;
            }
            ans[k] = x;
            nums[i] = c;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<int> colorTheArray(int n, vector<vector<int>>& queries) {
        vector<int> nums(n);
        vector<int> ans;
        int x = 0;
        for (auto& q : queries) {
            int i = q[0], c = q[1];
            if (i > 0 && nums[i] > 0 && nums[i - 1] == nums[i]) {
                --x;
            }
            if (i < n - 1 && nums[i] > 0 && nums[i + 1] == nums[i]) {
                --x;
            }
            if (i > 0 && nums[i - 1] == c) {
                ++x;
            }
            if (i < n - 1 && nums[i + 1] == c) {
                ++x;
            }
            ans.push_back(x);
            nums[i] = c;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
func colorTheArray(n int, queries [][]int) (ans []int) {
    nums := make([]int, n)
    x := 0
    for _, q := range queries {
        i, c := q[0], q[1]
        if i > 0 && nums[i] > 0 && nums[i-1] == nums[i] {
            x--
        }
        if i < n-1 && nums[i] > 0 && nums[i+1] == nums[i] {
            x--
        }
        if i > 0 && nums[i-1] == c {
            x++
        }
        if i < n-1 && nums[i+1] == c {
            x++
        }
        ans = append(ans, x)
        nums[i] = c
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
function colorTheArray(n: number, queries: number[][]): number[] {
    const nums: number[] = new Array(n).fill(0);
    const ans: number[] = [];
    let x = 0;
    for (const [i, c] of queries) {
        if (i > 0 && nums[i] > 0 && nums[i - 1] == nums[i]) {
            --x;
        }
        if (i < n - 1 && nums[i] > 0 && nums[i + 1] == nums[i]) {
            --x;
        }
        if (i > 0 && nums[i - 1] == c) {
            ++x;
        }
        if (i < n - 1 && nums[i + 1] == c) {
            ++x;
        }
        ans.push(x);
        nums[i] = c;
    }
    return ans;
}

Comments