You are given a 2D matrix of size m x n, consisting of non-negative integers. You are also given an integer k.
The value of coordinate (a, b) of the matrix is the XOR of all matrix[i][j] where 0 <= i <= a < m and 0 <= j <= b < n (0-indexed).
Find the kth largest value (1-indexed) of all the coordinates of matrix.
Example 1:
Input: matrix = [[5,2],[1,6]], k = 1 Output: 7 Explanation: 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 Explanation: 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 Explanation: The value of coordinate (1,0) is 5 XOR 1 = 4, which is the 3rd largest value.
Constraints:
m == matrix.lengthn == matrix[i].length1 <= m, n <= 10000 <= matrix[i][j] <= 1061 <= k <= m * nProblem Overview: You are given an m x n matrix. For every coordinate (i, j), compute the XOR of all elements in the submatrix from (0,0) to (i,j). This value is called the XOR coordinate value. After computing all m*n values, return the kth largest among them.
The core challenge is efficiently computing XOR values for every submatrix. Recomputing each region from scratch would be expensive, so the key idea is to reuse previously computed results using a prefix sum-style technique with XOR.
Approach 1: Prefix XOR + Min-Heap (O(mn log k) time, O(k) space)
Compute the XOR prefix for each cell using the relation px[i][j] = matrix[i][j] ^ px[i-1][j] ^ px[i][j-1] ^ px[i-1][j-1]. This works similarly to a 2D prefix sum but uses XOR operations. While iterating through the matrix, push each prefix XOR value into a min-heap of size k. If the heap grows beyond k, remove the smallest element. This keeps only the k largest XOR values seen so far, and the heap root becomes the answer.
The insight is that you do not need to store or sort all m*n values. A heap (priority queue) maintains the top k elements efficiently. Each matrix cell is processed once, making the traversal O(mn), while heap updates cost O(log k).
Approach 2: Prefix XOR + Sorting (O(mn log(mn)) time, O(mn) space)
First compute all XOR coordinate values using the same 2D prefix XOR formula. Store every computed value in an array. After processing the entire matrix, sort the array in descending order and return the element at index k-1.
This approach is straightforward and easy to implement. However, sorting all m*n values adds extra overhead compared to maintaining only the top k. For large matrices, O(mn log(mn)) becomes noticeably slower than the heap-based solution. Still, it remains a good option when code simplicity is preferred or when k is close to m*n.
Recommended for interviews: The prefix XOR with min-heap solution is typically expected. Interviewers want to see that you recognize the 2D prefix XOR pattern (a variant of prefix sum) and combine it with a priority queue to maintain the kth largest element efficiently. The sorting approach demonstrates understanding of the prefix XOR computation, but the heap solution shows stronger optimization skills.
We can use prefix XOR to quickly calculate the XOR value of any sub-matrix. The prefix XOR at (i, j) can be defined as the XOR of all elements from (0, 0) to (i, j). With this, the XOR for every coordinate can be derived quickly. To find the kth largest value among these, a min-heap of size k can be used, continually maintaining the largest k values observed so far.
This Python solution uses a min-heap to track the kth largest XOR value. We compute the prefix XOR for each element in the matrix, storing each result in the heap. If the heap exceeds size k, we remove the smallest item. Our final result is the smallest item in this size-k heap, which represents the kth largest XOR value.
Time Complexity: O(m * n * log k), where m is the number of rows and n is the number of columns.
Space Complexity: O(m * n + k).
An alternative approach is to calculate all possible XOR values using prefix XOR and then sort these values to directly find the kth largest. Although this method might have higher time complexity due to sorting, it is straightforward and utilizes built-in sorting algorithms for reliability.
This C solution calculates all XOR values using a prefix XOR approach, stores these values in an array, and sorts the array to quickly find the kth largest value. The use of qsort simplifies the sorting process.
C
JavaScript
Time Complexity: O(m * n log(m * n)), due to sorting.
Space Complexity: O(m * n) for storing XOR values.
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.,
$
s[i][j] = \bigoplus_{0 leq x leq i, 0 leq y leq j} matrix[x][y]
And s[i][j] can be calculated from the three elements s[i - 1][j], s[i][j - 1] and s[i - 1][j - 1], i.e.,
s[i][j] = s[i - 1][j] \oplus s[i][j - 1] \oplus s[i - 1][j - 1] \oplus matrix[i - 1][j - 1]
We traverse the matrix, calculate all s[i][j], then sort them, and finally return the kth largest element. If you don't want to use sorting, you can also use the quick selection algorithm, which can optimize the time complexity.
The time complexity is O(m times n times log (m times n)) or O(m times n), and the space complexity is O(m times n). Here, m and n$ are the number of rows and columns of the matrix, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Prefix XOR and Min-Heap | Time Complexity: O(m * n * log k), where m is the number of rows and n is the number of columns. |
| Prefix XOR and Sorting | Time Complexity: O(m * n log(m * n)), due to sorting. |
| Two-dimensional Prefix XOR + Sorting or Quick Selection | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix XOR + Min-Heap | O(mn log k) | O(k) | Best general solution when k is much smaller than m*n |
| Prefix XOR + Sorting | O(mn log(mn)) | O(mn) | Simple implementation when memory is not a concern |
LeetCode 1738. Find Kth Largest XOR Coordinate Value #leetcode #coding #cpp • yoBro • 1,305 views views
Watch 9 more video solutions →Practice Find Kth Largest XOR Coordinate Value with our built-in code editor and test cases.
Practice on FleetCode