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 withindexi
tovali
, overwriting any previous values. - if
typei == 1
, set the values in the column withindexi
tovali
, 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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|