Find Kth Largest XOR Coordinate Value
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.
Example 4:
Input: matrix = [[5,2],[1,6]], k = 4
Output: 0
Explanation: The value of coordinate (1,1) is 5 XOR 2 XOR 1 XOR 6 = 0, which is the 4th largest value.
Constraints:
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 1000
- 0 <= matrix[i][j] <= 106
- 1 <= k <= m * n
Solution:
class Solution {
public int kthLargestValue(int[][] matrix, int k) {
int m = matrix.length, n = matrix[0].length;
int[][] prefix = new int[m][n];
PriorityQueue<Integer> minHeap = new PriorityQueue();
prefix[0][0] = matrix[0][0];
offer(minHeap, prefix[0][0], k);
for (int i = 1; i < m; i ++) {
prefix[i][0] = prefix[i - 1][0] ^ matrix[i][0];
offer(minHeap, prefix[i][0], k);
}
for (int j = 1; j < n; j ++) {
prefix[0][j] = prefix[0][j - 1] ^ matrix[0][j];
offer(minHeap, prefix[0][j], k);
}
for (int i = 1; i < m; i ++) {
for (int j = 1; j < n; j ++) {
prefix[i][j] = prefix[i - 1][j] ^ prefix[i][j - 1] ^ prefix[i - 1][j - 1] ^ matrix[i][j];
offer(minHeap, prefix[i][j], k);
}
}
// for (int [] d : prefix) System.out.println(Arrays.toString(d));
// System.out.println(minHeap);
int res = minHeap.poll();
return res;
}
private void offer(PriorityQueue<Integer> minHeap, int val, int k) {
if (minHeap.size() < k) {
minHeap.offer(val);
} else if (minHeap.peek() < val) {
minHeap.poll();
minHeap.offer(val);
}
}
}