Watch 10 video solutions for Find Kth Largest XOR Coordinate Value, a medium level problem involving Array, Divide and Conquer, Bit Manipulation. This walkthrough by yoBro has 1,305 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |