Sum of Matrix After Queries solution and explanation
9 more videos on this problem
Leetcode Weekly contest 348 - Medium - Sum of Matrix After QueriesPrakhar Agrawal · 11:56 · 2K views
Sum of Matrix After Queries | leetcode Weekly 348 | Leetcode MediumBinaryMagic · 14:35 · 865 views
2718. Sum of Matrix After Queries | Binary Search | Leetcode Weekly Contest 348codingMohan · 22:16 · 537 views
2718. Sum of Matrix After Queries (Leetcode Medium)Programming Live with Larry · 8:30 · 313 views
Sum of Matrix After Queries | Leetcode 2718 | Weekly 348Tech Courses · 19:13 · 303 views
Sum of Matrix After Queries - Leetcode 2718 - PythonAlgorithms Casts · 17:16 · 216 views
【每日一题】LeetCode 2718. Sum of Matrix After QueriesHuifeng Guan · 9:47 · 216 views
[Eng] Leetcode Weekly Contest 348 | 2718. Sum of Matrix After QueriesCyCode · 12:04 · 161 views
Weekly Contest 348 - LeetCode || Question 3 || Question 2718let's code · 6:50 · 161 views
Sum of Matrix After Queries - LeetCode 2718 - Python Solution Code Answer ExplanationAlgoSkills · 12:23 · 123 views
The problem
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
Approach overview
Problem Overview: You start with an n x n matrix filled with zeros. Each query assigns a value to an entire row or column. After processing all queries, return the total sum of the matrix. The challenge is avoiding an expensive full matrix update for every query.
Approach 1: Direct Simulation with Efficient Storage (O(q * n) time, O(n) space)
The straightforward strategy simulates each query as it appears. For a row assignment, iterate across all n columns and update the row values; for a column assignment, iterate through all rows. Instead of storing the entire matrix, you can maintain row and column structures that represent current values and compute contributions to the total sum while applying updates. This reduces memory overhead but still performs O(n) work per query. When the number of queries is small or n is limited, this approach is simple and easy to implement using basic array operations.
Approach 2: Optimized Reverse Simulation (O(q) time, O(n) space)
The key observation: the last assignment to a row or column determines the final value of its cells. Instead of simulating forward, iterate through the queries in reverse. Maintain two hash table or set structures: one for rows already processed and one for columns already processed. When you encounter a row assignment that hasn’t been processed yet, it contributes value * (n - processedCols) to the total because only columns not finalized will keep that value. Mark the row as processed. Similarly, a column assignment contributes value * (n - processedRows). This eliminates repeated overwrites and ensures each row and column is counted at most once.
Reverse simulation works because later queries override earlier ones. By processing from the end, you capture only the assignments that actually survive in the final matrix. The algorithm touches each query once and performs constant-time lookups using sets, which makes it highly scalable even when n and the query count are large.
Recommended for interviews: The reverse simulation approach is what interviewers expect. Writing the direct simulation first shows you understand the mechanics of the problem, but recognizing that only the last assignment matters demonstrates stronger algorithmic insight. Efficient tracking with sets and careful counting of remaining rows or columns leads to the optimal O(q) solution.
Approach 1: Direct Simulation with Efficient Storage
Instead of updating a full matrix, which could be inefficient considering the constraints, we simulate the updates using arrays to keep track of row and column updates. This avoids the need to modify the entire matrix, thus saving computation time and space.
def sum_of_matrix_after_queries(n, queries):
row_updates = [-1] * n
col_updates = [-1] * n
row_values = [0] * n
col_values = [0] * n
last_row = -1
last_col = -1
for i, (q_type, index, value) in enumerate(queries):
if q_type == 0: # update row
row_updates[index] = i
row_values[index] = value
else: # update column
col_updates[index] = i
col_values[index] = value
total_sum = 0
for row in range(n):
for col in range(n):
if row_updates[row] > col_updates[col]:
total_sum += row_values[row]
else:
total_sum += col_values[col]
return total_sum
# Example usage:
# result = sum_of_matrix_after_queries(3, [[0,0,1],[1,2,2],[0,2,3],[1,0,4]])
# print(result) # Output: 23#include <stdio.h>
#include <stdlib.h>
int sumOfMatrixAfterQueries(int n, int queries[][3], int queriesSize) {
int *rowUpdates = (int *)malloc(n * sizeof(int));
int *colUpdates = (int *)malloc(n * sizeof(int));
int *rowValues = (int *)malloc(n * sizeof(int));
int *colValues = (int *)malloc(n * sizeof(int));
for (int i = 0; i < n; ++i) {
rowUpdates[i] = -1;
colUpdates[i] = -1;
rowValues[i] = 0;
colValues[i] = 0;
}
for (int i = 0; i < queriesSize; ++i) {
int type = queries[i][0];
int index = queries[i][1];
int val = queries[i][2];
if (type == 0) {
rowUpdates[index] = i;
rowValues[index] = val;
} else {
colUpdates[index] = i;
colValues[index] = val;
}
}
int totalSum = 0;
for (int row = 0; row < n; ++row) {
for (int col = 0; col < n; ++col) {
if (rowUpdates[row] > colUpdates[col]) {
totalSum += rowValues[row];
} else {
totalSum += colValues[col];
}
}
}
free(rowUpdates);
free(colUpdates);
free(rowValues);
free(colValues);
return totalSum;
}
// Example usage:
// int sampleQueries[4][3] = {{0,0,1}, {1,2,2}, {0,2,3}, {1,0,4}};
// int result = sumOfMatrixAfterQueries(3, sampleQueries, 4);
// printf("%d\n", result); // Output: 23This solution uses two arrays, one for row updates and another for column updates, to store the latest query operation on each row and column. The arrays row_updates and col_updates record the index of the last query that affected each row or column. The computation of the final matrix sum happens by choosing the latest applicable query update for each cell.
Time Complexity: O(n^2) - We iterate over all cells to compute the final sum.
Space Complexity: O(n) - We use auxiliary arrays for row and column update indices and values.
Approach 2: Optimized Reverse Simulation
By processing the queries in reverse order, we can efficiently manage the rows and columns to prevent unnecessary overwrites. By using flags to record rows and columns that have already been set, we can avoid redundant operations and achieve an optimized simulation.
#include <vector>
#include <unordered_set>
using namespace std;
int sumOfMatrixAfterQueries(int n, vector<vector<int>>& queries) {
vector<bool> rowSet(n, false), colSet(n, false);
int setRows = 0, setCols = 0, rowSum = 0, colSum = 0;
for (int i = queries.size() - 1; i >= 0; --i) {
int type = queries[i][0], index = queries[i][1], value = queries[i][2];
if (type == 0 && !rowSet[index]) { // row update
rowSum += (n - setCols) * value;
setRows++;
rowSet[index] = true;
}
else if (type == 1 && !colSet[index]) { // column update
colSum += (n - setRows) * value;
setCols++;
colSet[index] = true;
}
}
return rowSum + colSum;
}
// Example usage:
// vector<vector<int>> queries = {{0,0,1},{1,2,2},{0,2,3},{1,0,4}};
// int result = sumOfMatrixAfterQueries(3, queries);
// // Output: 23
function sumOfMatrixAfterQueries(n, queries) {
let rowSet = new Array(n).fill(false);
let colSet = new Array(n).fill(false);
let rowSum = 0, colSum = 0, setRows = 0, setCols = 0;
for (let i = queries.length - 1; i >= 0; i--) {
const [type, index, value] = queries[i];
if (type === 0 && !rowSet[index]) { // row update
rowSum += n * value - setCols * value;
setRows++;
rowSet[index] = true;
} else if (type === 1 && !colSet[index]) { // column update
colSum += n * value - setRows * value;
setCols++;
colSet[index] = true;
}
}
return rowSum + colSum;
}
// Example usage:
// result = sumOfMatrixAfterQueries(3, [[0,0,1],[1,2,2],[0,2,3],[1,0,4]]);
// console.log(result); // Output: 23This C++ solution leverages reverse processing of queries, optimizing performance by skipping already handled operations. Boolean vectors mark the finalized rows and columns, and we accumulate only relevant sums during the reverse iteration.
Time Complexity: O(q + n) - Processing each query and using constant space checks.
Space Complexity: O(n) - For flag vectors to mark row and column operations.
Approach 3: 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 theith row has been modified. If not, we addv times (n - |col|)to the answer, where|col|represents the size ofcol, and then additorow. - If
t = 1, we check whether theith column has been modified. If not, we addv times (n - |row|)to the answer, where|row|represents the size ofrow, and then additocol.
Finally, return the answer.
The time complexity is O(m), and the space complexity is O(n). Here, m represents the number of queries.
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;
}
}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;
}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
}Complexity comparison
| Approach | Complexity |
|---|---|
| Direct Simulation with Efficient Storage | Time Complexity: O(n^2) - We iterate over all cells to compute the final sum. |
| Optimized Reverse Simulation | Time Complexity: O(q + n) - Processing each query and using constant space checks. |
| Hash Table | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Simulation with Efficient Storage | O(q * n) | O(n) | When constraints are small or when implementing a quick baseline solution |
| Optimized Reverse Simulation | O(q) | O(n) | Best for large inputs where many queries overwrite previous updates |
Frequently asked questions
Is Sum of Matrix After Queries easy or hard?
The problem is rated Medium because the naive simulation is straightforward but inefficient. Recognizing that only the last assignment matters and applying reverse simulation requires a key insight that improves complexity to O(q).
Sum of Matrix After Queries Python/Java solution
Most implementations use the same reverse traversal logic across languages. Python solutions typically use sets for row and column tracking, while C++, JavaScript, or C implementations may use unordered_set or boolean arrays for O(1) checks.
How to solve Sum of Matrix After Queries in O(n)?
Process the queries in reverse order and keep two sets for rows and columns already assigned. When encountering a row assignment, add value * (n - processedColumns) if that row hasn't been counted yet. For column assignments, add value * (n - processedRows). This ensures each row and column contributes only once.
What is the best approach for Sum of Matrix After Queries?
The optimized reverse simulation approach is the most efficient. Process queries from the end while tracking which rows and columns have already been finalized using sets. Each row or column contributes to the total only once, producing an O(q) time solution with O(n) extra space.
Is Sum of Matrix After Queries asked at Google/Amazon/Meta?
Matrix query problems with optimization tricks appear frequently in interviews at companies like Amazon, Google, and Meta. Variants often test your ability to avoid repeated updates and instead reason about the final state using counting or reverse processing.
What data structure is used in Sum of Matrix After Queries?
The optimal approach uses hash sets (or hash tables) to track rows and columns that have already been processed. Arrays can also be used for constant-time lookups if the size is known in advance.
What is the time complexity of Sum of Matrix After Queries?
The optimal solution runs in O(q) time, where q is the number of queries. Each query is processed once during reverse traversal with constant-time set lookups. Space complexity is O(n) to track visited rows and columns.