Welcome to Subscribe On Youtube

2718. Sum of Matrix After Queries

Description

You are given an integer n and a 0-indexed 2D array queries where queries[i] = [typei, indexi, vali].

Initially, there is a 0-indexed n x n matrix filled with 0's. For each query, you must apply one of the following changes:

• if typei == 0, set the values in the row with indexi to vali, overwriting any previous values.
• if typei == 1, set the values in the column with indexi to vali, overwriting any previous values.

Return the sum of integers in the matrix after all queries are applied.

 

Example 1:

Input: n = 3, queries = [[0,0,1],[1,2,2],[0,2,3],[1,0,4]]
Output: 23
Explanation: The image above describes the matrix after each query. The sum of the matrix after all queries are applied is 23. 

Example 2:

Input: n = 3, queries = [[0,0,4],[0,1,2],[1,0,1],[0,2,3],[1,2,1]]
Output: 17
Explanation: The image above describes the matrix after each query. The sum of the matrix after all queries are applied is 17.

 

Constraints:

• 1 <= n <= 104
• 1 <= queries.length <= 5 * 104
• queries[i].length == 3
• 0 <= typei <= 1
• 0 <= indexi < n
• 0 <= vali <= 105

Solutions

Solution 1: Hash Table

Since the value of each row and column depends on the last modification, we can traverse all queries in reverse order and use hash tables $row$ and $col$ to record which rows and columns have been modified.

For each query $(t, i, v)$:

• If $t = 0$, we check whether the $i$th row has been modified. If not, we add $v \times (n -

  col

  )$ to the answer, where $

  col

  $ represents the size of $col$, and then add $i$ to $row$.

• If $t = 1$, we check whether the $i$th column has been modified. If not, we add $v \times (n -

  row

  )$ to the answer, where $

  row

  $ represents the size of $row$, and then add $i$ to $col$.

Finally, return the answer.

The time complexity is $O(m)$, and the space complexity is $O(n)$. Here, $m$ represents the number of queries.

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public long matrixSumQueries(int n, int[][] queries) {
          Set<Integer> row = new HashSet<>();
          Set<Integer> col = new HashSet<>();
          int m = queries.length;
          long ans = 0;
          for (int k = m - 1; k >= 0; --k) {
              var q = queries[k];
              int t = q[0], i = q[1], v = q[2];
              if (t == 0) {
                  if (row.add(i)) {
                      ans += 1L * (n - col.size()) * v;
                  }
              } else {
                  if (col.add(i)) {
                      ans += 1L * (n - row.size()) * v;
                  }
              }
          }
          return ans;
      }
  }
  

• class Solution {
  public:
      long long matrixSumQueries(int n, vector<vector<int>>& queries) {
          unordered_set<int> row, col;
          reverse(queries.begin(), queries.end());
          long long ans = 0;
          for (auto& q : queries) {
              int t = q[0], i = q[1], v = q[2];
              if (t == 0) {
                  if (!row.count(i)) {
                      ans += 1LL * (n - col.size()) * v;
                      row.insert(i);
                  }
              } else {
                  if (!col.count(i)) {
                      ans += 1LL * (n - row.size()) * v;
                      col.insert(i);
                  }
              }
          }
          return ans;
      }
  };
  

• class Solution:
      def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:
          row = set()
          col = set()
          ans = 0
          for t, i, v in queries[::-1]:
              if t == 0:
                  if i not in row:
                      ans += v * (n - len(col))
                      row.add(i)
              else:
                  if i not in col:
                      ans += v * (n - len(row))
                      col.add(i)
          return ans
  
  

• func matrixSumQueries(n int, queries [][]int) (ans int64) {
  	row, col := map[int]bool{}, map[int]bool{}
  	m := len(queries)
  	for k := m - 1; k >= 0; k-- {
  		t, i, v := queries[k][0], queries[k][1], queries[k][2]
  		if t == 0 {
  			if !row[i] {
  				ans += int64(v * (n - len(col)))
  				row[i] = true
  			}
  		} else {
  			if !col[i] {
  				ans += int64(v * (n - len(row)))
  				col[i] = true
  			}
  		}
  	}
  	return
  }
  

• function matrixSumQueries(n: number, queries: number[][]): number {
      const row: Set<number> = new Set();
      const col: Set<number> = new Set();
      let ans = 0;
      queries.reverse();
      for (const [t, i, v] of queries) {
          if (t === 0) {
              if (!row.has(i)) {
                  ans += v * (n - col.size);
                  row.add(i);
              }
          } else {
              if (!col.has(i)) {
                  ans += v * (n - row.size);
                  col.add(i);
              }
          }
      }
      return ans;
  }
  
  

All Problems

All Solutions