Problem

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 adjacent pairs in colors set to 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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


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

1
2
3
4
5
6
7
8
9


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

Solution

Method 1 -

Intuition

We need to efficiently track the number of adjacent pairs with the same color after each query. Since only one element changes per query, we can update the count by checking the affected neighbors before and after the change.

Approach

For each query, before updating, check if the left/right neighbor forms a same-color pair with the current index and subtract from the count if so. After updating, check again and add to the count if a new pair is formed. This way, we avoid recomputing the entire array each time.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

vector<int> colorTheArray(int n, vector<vector<int>>& queries) {
    vector<int> colors(n, 0);
    int cnt = 0;
    vector<int> res;
    for (auto& q : queries) {
        int i = q[0], c = q[1];
        if (colors[i] != 0) {
            if (i > 0 && colors[i] == colors[i-1]) cnt--;
            if (i < n-1 && colors[i] == colors[i+1]) cnt--;
        }
        colors[i] = c;
        if (i > 0 && colors[i] == colors[i-1]) cnt++;
        if (i < n-1 && colors[i] == colors[i+1]) cnt++;
        res.push_back(cnt);
    }
    return res;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func colorTheArray(n int, queries [][]int) []int {
    colors := make([]int, n)
    cnt := 0
    res := make([]int, 0, len(queries))
    for _, q := range queries {
        i, c := q[0], q[1]
        if colors[i] != 0 {
            if i > 0 && colors[i] == colors[i-1] { cnt-- }
            if i < n-1 && colors[i] == colors[i+1] { cnt-- }
        }
        colors[i] = c
        if i > 0 && colors[i] == colors[i-1] { cnt++ }
        if i < n-1 && colors[i] == colors[i+1] { cnt++ }
        res = append(res, cnt)
    }
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

public int[] colorTheArray(int n, int[][] queries) {
    int[] colors = new int[n];
    int cnt = 0;
    int[] res = new int[queries.length];
    for (int k = 0; k < queries.length; k++) {
        int i = queries[k][0], c = queries[k][1];
        if (colors[i] != 0) {
            if (i > 0 && colors[i] == colors[i-1]) cnt--;
            if (i < n-1 && colors[i] == colors[i+1]) cnt--;
        }
        colors[i] = c;
        if (i > 0 && colors[i] == colors[i-1]) cnt++;
        if (i < n-1 && colors[i] == colors[i+1]) cnt++;
        res[k] = cnt;
    }
    return res;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

fun colorTheArray(n: Int, queries: Array<IntArray>): IntArray {
    val colors = IntArray(n)
    var cnt = 0
    val res = IntArray(queries.size)
    for (k in queries.indices) {
        val i = queries[k][0]
        val c = queries[k][1]
        if (colors[i] != 0) {
            if (i > 0 && colors[i] == colors[i-1]) cnt--
            if (i < n-1 && colors[i] == colors[i+1]) cnt--
        }
        colors[i] = c
        if (i > 0 && colors[i] == colors[i-1]) cnt++
        if (i < n-1 && colors[i] == colors[i+1]) cnt++
        res[k] = cnt
    }
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

from typing import List

def colorTheArray(n: int, queries: List[List[int]]) -> List[int]:
    colors = [0] * n
    cnt = 0
    res = []
    for i, c in queries:
        if colors[i] != 0:
            if i > 0 and colors[i] == colors[i-1]:
                cnt -= 1
            if i < n-1 and colors[i] == colors[i+1]:
                cnt -= 1
        colors[i] = c
        if i > 0 and colors[i] == colors[i-1]:
            cnt += 1
        if i < n-1 and colors[i] == colors[i+1]:
            cnt += 1
        res.append(cnt)
    return res
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

impl Solution {
    pub fn color_the_array(n: i32, queries: Vec<Vec<i32>>) -> Vec<i32> {
        let n = n as usize;
        let mut colors = vec![0; n];
        let mut cnt = 0;
        let mut res = Vec::with_capacity(queries.len());
        for q in queries.iter() {
            let i = q[0] as usize;
            let c = q[1];
            if colors[i] != 0 {
                if i > 0 && colors[i] == colors[i-1] { cnt -= 1; }
                if i + 1 < n && colors[i] == colors[i+1] { cnt -= 1; }
            }
            colors[i] = c;
            if i > 0 && colors[i] == colors[i-1] { cnt += 1; }
            if i + 1 < n && colors[i] == colors[i+1] { cnt += 1; }
            res.push(cnt);
        }
        res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

function colorTheArray(n: number, queries: number[][]): number[] {
    const colors = new Array(n).fill(0);
    let cnt = 0;
    const res: number[] = [];
    for (const [i, c] of queries) {
        if (colors[i] !== 0) {
            if (i > 0 && colors[i] === colors[i-1]) cnt--;
            if (i < n-1 && colors[i] === colors[i+1]) cnt--;
        }
        colors[i] = c;
        if (i > 0 && colors[i] === colors[i-1]) cnt++;
        if (i < n-1 && colors[i] === colors[i+1]) cnt++;
        res.push(cnt);
    }
    return res;
}

Complexity

  • ⏰ Time complexity: O(q) where q = number of queries (each query is processed in O(1)).
  • 🧺 Space complexity: O(n) for the colors array.