How does the prefix XOR matrix work for this problem?

Each cell stores the XOR of all elements from the top-left to that cell, allowing constant-time computation for each coordinate value.

Can I use sorting to find the kth largest?

Sorting works but is inefficient for large matrices; using a heap or quickselect reduces time complexity significantly.

Does this approach work for negative numbers?

XOR coordinate values assume non-negative integers; negative numbers may produce unexpected results with prefix XOR.

What is the main failure mode in this problem?

Recomputing XOR for every coordinate instead of using the prefix matrix leads to timeouts on large datasets.

How does this connect to the Array plus Divide and Conquer pattern?

The problem divides the 2D array into submatrices conceptually, using prefix XOR to conquer overlapping computations efficiently.

#1738

Medium

auto_awesome堆

LeetCode 题解工作台

找出第 K 大的异或坐标值

给你一个二维矩阵 matrix 和一个整数 k ，矩阵大小为 m x n 由非负整数组成。矩阵中坐标 (a, b) 的目标值可以通过对所有元素 matrix[i][j] 执行异或运算得到，其中 i 和 j 满足 0 且 0 （下标从 0 开始计数）。请你找出 matrix 的所有坐标中第…

数组分治位运算排序堆（优先队列）

题目描述

给你一个二维矩阵 matrix 和一个整数 k ，矩阵大小为 m x n 由非负整数组成。

矩阵中坐标 (a, b) 的 目标值 可以通过对所有元素 matrix[i][j] 执行异或运算得到，其中 i 和 j 满足 0 <= i <= a < m 且 0 <= j <= b < n（下标从 0 开始计数）。

请你找出 matrix 的所有坐标中第 k 大的目标值（k 的值从 1 开始计数）。

示例 1：

输入：matrix = [[5,2],[1,6]], k = 1
输出：7
解释：坐标 (0,1) 的目标值是 5 XOR 2 = 7 ，为最大的目标值。

示例 2：

输入：matrix = [[5,2],[1,6]], k = 2
输出：5
解释：坐标 (0,0) 的目标值是 5 = 5 ，为第 2 大的目标值。

示例 3：

输入：matrix = [[5,2],[1,6]], k = 3
输出：4
解释：坐标 (1,0) 的目标值是 5 XOR 1 = 4 ，为第 3 大的目标值。

示例 4：

输入：matrix = [[5,2],[1,6]], k = 4
输出：0
解释：坐标 (1,1) 的目标值是 5 XOR 2 XOR 1 XOR 6 = 0 ，为第 4 大的目标值。

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 1000
0 <= matrix[i][j] <= 10⁶
1 <= k <= m * n

lightbulb

解题思路

方法一：二维前缀异或 + 排序或快速选择

我们定义一个二维前缀异或数组 $s$ ，其中 $s[i][j]$ 表示矩阵前 $i$ 行和前 $j$ 列的元素异或运算的结果，即：

s[i][j] = \bigoplus_{0 \leq x \leq i, 0 \leq y \leq j} matrix[x][y]

而 $s[i][j]$ 可以由 $s[i - 1][j]$ , $s[i][j - 1]$ 和 $s[i - 1][j - 1]$ 三个元素计算得到，即：

s[i][j] = s[i - 1][j] \oplus s[i][j - 1] \oplus s[i - 1][j - 1] \oplus matrix[i - 1][j - 1]

我们遍历矩阵，计算出所有的 $s[i][j]$ ，然后将其排序，最后返回第 $k$ 大的元素即可。如果不想使用排序，也可以使用快速选择算法，这样可以优化时间复杂度。

时间复杂度 $O(m \times n \times \log (m \times n))$ 或 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def kthLargestValue(self, matrix: List[List[int]], k: int) -> int:
        m, n = len(matrix), len(matrix[0])
        s = [[0] * (n + 1) for _ in range(m + 1)]
        ans = []
        for i in range(m):
            for j in range(n):
                s[i + 1][j + 1] = s[i + 1][j] ^ s[i][j + 1] ^ s[i][j] ^ matrix[i][j]
                ans.append(s[i + 1][j + 1])
        return nlargest(k, ans)[-1]

speed

复杂度分析

指标	值
时间	complexity is O(m _n) for building the prefix XOR matrix plus O(m_ n) for flattening and O(k log (m _n)) for heap selection, or O(m_ n) for quickselect. Space complexity is O(m _n) for the prefix matrix and O(m_ n) for storing coordinate values before selection.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ask about reducing redundant XOR calculations for each coordinate.
question_mark
Probe whether candidate can apply 2D prefix sums correctly to XOR instead of sum.
question_mark
Check if candidate optimizes selection using heap or quickselect for kth largest.

warning

常见陷阱

外企场景

error
Recomputing XOR for each coordinate without prefix array, causing TLE on large matrices.
error
Incorrect prefix XOR relation leading to wrong values in certain coordinates.
error
Sorting the entire list instead of using selection methods, wasting time and memory.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find kth smallest XOR coordinate instead of largest, requiring reversed selection logic.
arrow_right_alt
Compute XOR sums for submatrices of arbitrary size rather than from (0,0).
arrow_right_alt
Combine with dynamic updates where matrix elements change and kth largest must be recalculated efficiently.

help

常见问题

外企场景

继续练习

#1878 矩阵中最大的三个菱形和 #347 前 K 个高频元素 #1094 拼车