Sum of Matrix After Queries
MedPrompt
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 withindexitovali, overwriting any previous values. - if
typei == 1, set the values in the column withindexitovali, 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 <= 1041 <= queries.length <= 5 * 104queries[i].length == 30 <= typei <= 10 <= indexi < n0 <= vali <= 105
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. It involves creating an n x n matrix and applying each query one by one by updating the corresponding row or column. After all queries are applied, it calculates the sum of all elements in the matrix by iterating through it.
Algorithm
- Initialize an
n x nmatrix,grid, with all elements set to 0. - Iterate through each query
[type, index, val]in thequeriesarray. - If
typeis 0, it's a row update. Iterate through all columnsjfrom 0 ton-1and setgrid[index][j] = val. - If
typeis 1, it's a column update. Iterate through all rowsifrom 0 ton-1and setgrid[i][index] = val. - After processing all queries, initialize a variable
sumto 0. - Iterate through the entire
grid(both rows and columns) and add each element's value tosum. - Return the final
sum.
Walkthrough
The brute-force method is the most straightforward way to solve the problem. It follows the problem description literally.
First, we create an actual n x n matrix and initialize all its cells to zero. Then, we iterate through the list of queries. For each query, we perform the specified operation: if it's a row update, we iterate through that entire row and set each cell to the given value; if it's a column update, we do the same for the specified column. After executing all the queries, we perform a final pass over the entire matrix to sum up all the cell values to get the result.
class Solution { public long matrixSumQueries(int n, int[][] queries) { int[][] matrix = new int[n][n]; for (int[] query : queries) { int type = query[0]; int index = query[1]; int val = query[2]; if (type == 0) { // Row update for (int j = 0; j < n; j++) { matrix[index][j] = val; } } else { // Column update for (int i = 0; i < n; i++) { matrix[i][index] = val; } } } long sum = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { sum += matrix[i][j]; } } return sum; }}Complexity
Time
O(q * n + n^2) - Let `q` be the number of queries. Each query requires iterating through `n` elements, leading to O(q * n) for processing all queries. The final summation takes O(n^2). For the given constraints, this is too slow and will time out.
Space
O(n^2) - We need to store the entire `n x n` matrix in memory. For `n = 10^4`, this would be `10^8` integers, which is about 400MB and might exceed memory limits.
Trade-offs
Pros
Simple to understand and implement.
Directly follows the problem statement, making the logic easy to verify.
Cons
Highly inefficient in both time and space for the given constraints.
Will likely result in Time Limit Exceeded (TLE) due to the O(q * n) complexity.
May result in Memory Limit Exceeded (MLE) for large
ndue to the O(n^2) space requirement.
Solutions
Solution
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; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.