Skip to content

2672. Number of Adjacent Elements With the Same Color

  • Time: $O(n + q)$
  • Space: $O(n + q)$
 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
27
28
29
class Solution {
 public:
  vector<int> colorTheArray(int n, vector<vector<int>>& queries) {
    vector<int> ans;
    vector<int> arr(n);
    int sameColors = 0;

    for (const vector<int>& query : queries) {
      const int i = query[0];
      const int color = query[1];
      if (i + 1 < n) {
        if (arr[i + 1] > 0 && arr[i + 1] == arr[i])
          --sameColors;
        if (arr[i + 1] == color)
          ++sameColors;
      }
      if (i > 0) {
        if (arr[i - 1] > 0 && arr[i - 1] == arr[i])
          --sameColors;
        if (arr[i - 1] == color)
          ++sameColors;
      }
      arr[i] = color;
      ans.push_back(sameColors);
    }

    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
27
28
class Solution {
  public int[] colorTheArray(int n, int[][] queries) {
    int[] ans = new int[queries.length];
    int[] arr = new int[n];
    int sameColors = 0;

    for (int i = 0; i < queries.length; ++i) {
      final int j = queries[i][0];
      final int color = queries[i][1];
      if (j + 1 < n) {
        if (arr[j + 1] > 0 && arr[j + 1] == arr[j])
          --sameColors;
        if (arr[j + 1] == color)
          ++sameColors;
      }
      if (j > 0) {
        if (arr[j - 1] > 0 && arr[j - 1] == arr[j])
          --sameColors;
        if (arr[j - 1] == color)
          ++sameColors;
      }
      arr[j] = color;
      ans[i] = sameColors;
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
  def colorTheArray(self, n: int, queries: list[list[int]]) -> list[int]:
    ans = []
    arr = [0] * n
    sameColors = 0

    for i, color in queries:
      if i + 1 < n:
        if arr[i + 1] > 0 and arr[i + 1] == arr[i]:
          sameColors -= 1
        if arr[i + 1] == color:
          sameColors += 1
      if i > 0:
        if arr[i - 1] > 0 and arr[i - 1] == arr[i]:
          sameColors -= 1
        if arr[i - 1] == color:
          sameColors += 1
      arr[i] = color
      ans.append(sameColors)

    return ans