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.

#2718

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

查询后矩阵的和

给你一个整数 n 和一个下标从 0 开始的二维数组 queries ，其中 queries[i] = [type i , index i , val i ] 。一开始，给你一个下标从 0 开始的 n x n 矩阵，所有元素均为 0 。每一个查询，你需要执行以下操作之一：如果 type i ==…

数组哈希表

题目描述

给你一个整数 n 和一个下标从 0 开始的 二维数组 queries ，其中 queries[i] = [type_i, index_i, val_i] 。

一开始，给你一个下标从 0 开始的 n x n 矩阵，所有元素均为 0 。每一个查询，你需要执行以下操作之一：

如果 type_i == 0 ，将第 index_i 行的元素全部修改为 val_i ，覆盖任何之前的值。
如果 type_i == 1 ，将第 index_i 列的元素全部修改为 val_i ，覆盖任何之前的值。

请你执行完所有查询以后，返回矩阵中所有整数的和。

示例 1：

输入：n = 3, queries = [[0,0,1],[1,2,2],[0,2,3],[1,0,4]]
输出：23
解释：上图展示了每个查询以后矩阵的值。所有操作执行完以后，矩阵元素之和为 23 。

示例 2：

输入：n = 3, queries = [[0,0,4],[0,1,2],[1,0,1],[0,2,3],[1,2,1]]
输出：17
解释：上图展示了每一个查询操作之后的矩阵。所有操作执行完以后，矩阵元素之和为 17 。

提示：

1 <= n <= 10⁴
1 <= queries.length <= 5 * 10⁴
queries[i].length == 3
0 <= type_i <= 1
0 <= index_i < n
0 <= val_i <= 10⁵

lightbulb

解题思路

方法一：哈希表

由于每一行、每一列的值取决于最后一次的修改，因此，我们不妨倒序遍历所有的查询，使用哈希表 $row$ 和 $col$ 记录有哪些行和列被修改过。

对于每一次查询 $(t, i, v)$ ：

如果 $t = 0$ ，那么我们判断第 $i$ 行是否被修改过，如果没有，那么我们将 $v \times (n - |col|)$ 累加到答案中，其中 $|col|$ 表示 $col$ 的大小，然后将 $i$ 加入 $row$ 中；
如果 $t = 1$ ，那么我们判断第 $i$ 列是否被修改过，如果没有，那么我们将 $v \times (n - |row|)$ 累加到答案中，其中 $|row|$ 表示 $row$ 的大小，然后将 $i$ 加入 $col$ 中。

最后返回答案。

时间复杂度 $O(m)$ ，空间复杂度 $O(n)$ 。其中 $m$ 表示查询的次数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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

speed

复杂度分析

指标	值
时间	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.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#2713 矩阵中严格递增的单元格数 #2711 对角线上不同值的数量差 #2707 字符串中的额外字符