#1738

Medium

auto_awesomeArray plus Divide and Conquer

LeetCode Problem Workspace

Find Kth Largest XOR Coordinate Value

Compute the kth largest XOR coordinate in a 2D matrix using prefix sums, bit manipulation, and optimized selection techniques.

array divide and conquer bit manipulation sorting heap priority queue

Problem Statement

Given an m x n matrix of non-negative integers and an integer k, each coordinate (i, j) has a value defined as the XOR of all elements matrix[a][b] where 0 <= a <= i and 0 <= b <= j. Compute this XOR value for every coordinate efficiently.

Return the kth largest coordinate value among all m*n coordinates in the matrix. Optimize for large matrices by leveraging prefix XOR sums to avoid recalculating overlapping submatrices.

Examples

Example 1

Input: matrix = [[5,2],[1,6]], k = 1

Output: 7

The value of coordinate (0,1) is 5 XOR 2 = 7, which is the largest value.

Example 2

Input: matrix = [[5,2],[1,6]], k = 2

Output: 5

The value of coordinate (0,0) is 5 = 5, which is the 2nd largest value.

Example 3

Input: matrix = [[5,2],[1,6]], k = 3

Output: 4

The value of coordinate (1,0) is 5 XOR 1 = 4, which is the 3rd largest value.

Constraints

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

Solution Approach

Compute 2D Prefix XOR Matrix

Iterate through the matrix and build a prefix XOR array where each cell represents the XOR of all elements from the top-left corner to that cell. Use the relation prefix[i][j] = matrix[i][j] XOR prefix[i-1][j] XOR prefix[i][j-1] XOR prefix[i-1][j-1] to avoid recalculating overlapping submatrices.

Flatten and Select

Flatten the 2D prefix XOR matrix into a 1D array of all coordinate values. Use a heap of size k or the quickselect algorithm to efficiently determine the kth largest value without sorting the entire array, which is critical for large m and n.

Return Kth Largest Result

After computing the kth largest value using the heap or quickselect, return this value directly. This approach ensures O(m*n) for prefix computation and O(k log n) or O(n) for selection, balancing space and speed.

Complexity Analysis

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

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

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Two-dimensional Prefix XOR + Sorting or Quick Selection

We define a two-dimensional prefix XOR array $s$, where $s[i][j]$ represents the XOR result of the elements in the first $i$ rows and the first $j$ columns of the matrix, i.e.,

1

2

3

4

5

6

7

8

9

10

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]

Continue Practicing

#1878 get biggest three rhombus sums in a grid #347 top k frequent elements #1094 car pooling