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.
A much more efficient approach is to realize that later queries overwrite the effects of earlier ones. The final value of a cell is determined by the last query that affects its row or column. By processing the queries in reverse order, we can calculate the sum without building the matrix. We only need to consider the first time we encounter a row or column (when iterating backward), as this corresponds to the last update applied to it. We keep track of which rows and columns have been 'set' and calculate their contribution to the total sum.
Algorithm
- Initialize two boolean arrays,
seenRowof sizenandseenColof sizen, to allfalse. These will track which rows/columns have been finalized. - Initialize
totalSum = 0,rowCount = 0(count of finalized rows), andcolCount = 0(count of finalized columns). - Iterate through the
queriesarray in reverse order (fromqueries.length - 1down to0). - For each query
[type, index, val]:- If it's a row query (
type == 0) andseenRow[index]isfalse:- This is the last update for this row. Its contribution to the sum is
valmultiplied by the number of columns not yet finalized, which isn - colCount. - Add
(long) val * (n - colCount)tototalSum. - Mark the row as seen:
seenRow[index] = true, and incrementrowCount.
- This is the last update for this row. Its contribution to the sum is
- If it's a column query (
type == 1) andseenCol[index]isfalse:- This is the last update for this column. Its contribution is
valmultiplied by the number of rows not yet finalized,n - rowCount. - Add
(long) val * (n - rowCount)tototalSum. - Mark the column as seen:
seenCol[index] = true, and incrementcolCount.
- This is the last update for this column. Its contribution is
- If it's a row query (
- After the loop finishes,
totalSumwill hold the final sum of the matrix.
Walkthrough
The key observation is that the final state of the matrix only depends on the last query that sets a given row or column. Instead of simulating the process forward, we can determine the final sum by processing queries backward.
We iterate from the last query to the first. We use two boolean arrays, seenRow and seenCol, to keep track of rows and columns for which we've already determined their final value. When we process a query for a row (or column) that we haven't seen yet, we know this is its final state. The value val from this query will be applied to all cells in that row (or column) that are not overwritten by an even later query (which, in our backward pass, means a column/row we've already processed).
For a row query [0, index, val], if seenRow[index] is false, we add val * (n - colCount) to our total sum, where colCount is the number of columns we've already seen and finalized. We then mark this row as seen. A similar logic applies to column queries.
class Solution { public long matrixSumQueries(int n, int[][] queries) { boolean[] seenRow = new boolean[n]; boolean[] seenCol = new boolean[n]; int rowCount = 0; int colCount = 0; long totalSum = 0; // Iterate backwards from the last query for (int i = queries.length - 1; i >= 0; i--) { int type = queries[i][0]; int index = queries[i][1]; int val = queries[i][2]; if (type == 0) { // Row query if (!seenRow[index]) { // This is the last update for this row. // The number of cells in this row that are not yet set by a later column query is n - colCount. totalSum += (long) val * (n - colCount); seenRow[index] = true; rowCount++; } } else { // Column query if (!seenCol[index]) { // This is the last update for this column. // The number of cells in this column that are not yet set by a later row query is n - rowCount. totalSum += (long) val * (n - rowCount); seenCol[index] = true; colCount++; } } } return totalSum; }}Complexity
Time
O(q) - We iterate through the `queries` array once. Each operation inside the loop is constant time.
Space
O(n) - We use two boolean arrays of size `n` to keep track of seen rows and columns.
Trade-offs
Pros
Highly efficient in both time and space.
Avoids creating the large
n x nmatrix, thus saving significant memory.Easily passes the given constraints.
Cons
The logic is less direct than the brute-force approach and requires the key insight of processing queries in reverse.
Requires careful handling of counts to correctly calculate the contribution of each query.
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; }}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 ansVideo 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.