#2718

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Sum of Matrix After Queries

Calculate the total sum of a zero-filled n x n matrix after sequentially applying row and column update queries efficiently.

array hash table

Problem Statement

You are given an integer n and a list of queries where each query is represented as [type, index, value]. The matrix starts as an n x n grid of zeros, and each query instructs you to update either an entire row or an entire column with a specified value.

After processing all queries, return the sum of all integers in the matrix. Optimize by considering the latest query for each row or column, since earlier updates can be overwritten, following the array scanning plus hash lookup strategy.

Examples

Example 1

Input: n = 3, queries = [[0,0,1],[1,2,2],[0,2,3],[1,0,4]]

Output: 23

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

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

Solution Approach

Reverse Process Queries

Iterate over queries from last to first so that the most recent changes to rows and columns are applied first. This ensures that overwritten updates are ignored, reducing redundant calculations.

Use Hash Sets to Track Updates

Maintain two hash sets for rows and columns that have already been updated. Skip any query affecting a row or column already in the corresponding set, which follows the exact pattern of array scanning plus hash lookup.

Compute Matrix Sum Efficiently

For each query that modifies a new row or column, multiply the value by the number of unaffected cells in that row or column. Accumulate this product to compute the final matrix sum without building the full matrix.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(q + n) where q is the number of queries, since each query is checked at most once using hash sets. Space complexity is O(n) for tracking updated rows and columns, avoiding full matrix storage.

What Interviewers Usually Probe

Ask about efficient handling of large n and query lists using hash sets.
Look for recognition that processing queries in reverse simplifies sum calculation.
Expect candidate to avoid naive O(n^2 * q) approaches due to overwriting updates.

Common Pitfalls or Variants

Common pitfalls

Updating the entire matrix for each query leads to timeouts on large inputs.
Ignoring reverse processing may result in double-counting overwritten values.
Forgetting to account for already updated rows or columns causes incorrect sums.

Follow-up variants

Calculate the sum after queries if updates increment rather than overwrite previous values.
Handle a rectangular m x n matrix instead of a square n x n matrix.
Return the sum after only a subset of queries, testing partial update tracking.

FAQ

What is the main pattern used in Sum of Matrix After Queries?

The core pattern is array scanning plus hash lookup, tracking updated rows and columns to efficiently calculate the sum.

Why should queries be processed in reverse order?

Processing in reverse ensures the most recent updates are applied first, preventing earlier updates from being incorrectly counted.

Can we build the full matrix to solve this problem?

Building the full matrix is inefficient and can cause timeouts; incremental summation with hash sets is preferred.

How do hash sets optimize this problem?

Hash sets track which rows and columns are already updated, allowing each query to contribute to the sum only once.

What if a row and a column overlap in updates?

Only count values for cells that have not been previously updated in either row or column, ensuring no double-counting.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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 ans

Continue Practicing

#2713 maximum strictly increasing cells in a matrix #2711 difference of number of distinct values on diagonals #2707 extra characters in a string