LeetCode 1738: Find Kth Largest XOR Coordinate Value
Problem Description
Explanation
To solve this problem, we can create a prefix XOR matrix based on the given matrix. Then, we can iterate over all possible coordinates and store the XOR values in a min heap of size k. Finally, the top element of the heap will be the kth largest XOR coordinate value.
- Create a prefix XOR matrix by iterating over the given matrix and calculating the XOR values.
- Iterate over all possible coordinates (a, b) and calculate the XOR value using the prefix XOR matrix.
- Maintain a min heap of size k to store the k largest XOR values.
- Return the top element of the heap as the kth largest XOR coordinate value.
Time Complexity: O(m * n * log k)
Space Complexity: O(m * n + k)
Solutions
import java.util.PriorityQueue;
class Solution {
public int kthLargestValue(int[][] matrix, int k) {
int m = matrix.length;
int n = matrix[0].length;
int[][] prefixXOR = new int[m][n];
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int left = j > 0 ? prefixXOR[i][j - 1] : 0;
int top = i > 0 ? prefixXOR[i - 1][j] : 0;
int topLeft = (i > 0 && j > 0) ? prefixXOR[i - 1][j - 1] : 0;
prefixXOR[i][j] = matrix[i][j] ^ left ^ top ^ topLeft;
minHeap.offer(prefixXOR[i][j]);
if (minHeap.size() > k) {
minHeap.poll();
}
}
}
return minHeap.peek();
}
}Loading editor...