Sum of Matrix After Queries - Video Solutions

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.