Skip to content

2718. Sum of Matrix After Queries 👍

  • Time: $O(n + q)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  long long matrixSumQueries(int n, vector<vector<int>>& queries) {
    long ans = 0;
    // seen[0] := row, seen[1] := col
    vector<vector<bool>> seen(2, vector<bool>(n));
    // notSet[0] = row, notSet[1] := col
    vector<int> notSet(2, n);

    // Later queries dominate.
    for (int i = queries.size() - 1; i >= 0; --i) {
      const int type = queries[i][0];
      const int index = queries[i][1];
      const int val = queries[i][2];
      if (!seen[type][index]) {
        ans += val * notSet[type ^ 1];
        seen[type][index] = true;
        --notSet[type];
      }
    }

    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
class Solution {
  public long matrixSumQueries(int n, int[][] queries) {
    long ans = 0;
    // seen[0] := row, seen[1] := col
    boolean[][] seen = new boolean[2][n];
    // notSet[0] = row, notSet[1] := col
    int[] notSet = new int[2];
    Arrays.fill(notSet, n);

    // Late queries dominate.
    for (int i = queries.length - 1; i >= 0; --i) {
      final int type = queries[i][0];
      final int index = queries[i][1];
      final int val = queries[i][2];
      if (!seen[type][index]) {
        ans += val * notSet[type ^ 1];
        seen[type][index] = true;
        --notSet[type];
      }
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def matrixSumQueries(self, n: int, queries: list[list[int]]) -> int:
    ans = 0
    # seen[0] := row, seen[1] := col
    seen = [[False] * n for _ in range(2)]
    # notSet[0] = row, notSet[1] := col
    notSet = [n] * 2

    # Late queries dominate.
    for type, index, val in reversed(queries):
      if not seen[type][index]:
        ans += val * notSet[type ^ 1]
        seen[type][index] = True
        notSet[type] -= 1

    return ans