Skip to main content
Talentd

Sum of Matrix After Queries - Solution & Explanation

MediumArrayHash Table12 min read
Practice this problem

Problem Statement

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

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.

This 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.

Code

PythonC

Python

C

Complexity

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.

Try this approach in the editor →

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.

This JavaScript solution processes queries in reverse to track which rows and columns have been set. By using boolean arrays to mark applied operations, we accumulate sums only for the first (in reverse order) applicable update, thus minimizing redundant calculations.

Code

JavaScriptC++

JavaScript

C++

Complexity

Time Complexity: O(q + n) - We iterate over queries and use constant space checks.
Space Complexity: O(n) - We use flag arrays for row and column operations.

Try this approach in the editor →

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 the ith 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 ith 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Direct Simulation with Efficient Storage

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.

Optimized Reverse Simulation

Time Complexity: O(q + n) - We iterate over queries and use constant space checks.
Space Complexity: O(n) - We use flag arrays for row and column operations.

Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct Simulation with Efficient StorageO(q * n)O(n)When constraints are small or when implementing a quick baseline solution
Optimized Reverse SimulationO(q)O(n)Best for large inputs where many queries overwrite previous updates

Video Solution

Leetcode Weekly contest 348 - Medium - Sum of Matrix After Queries • Prakhar Agrawal • 2,143 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Sum of Matrix After Queries with our built-in code editor and test cases.

Practice on FleetCode
Previous

Range Addition II

Next

Range Sum Query 2D - Mutable