Formatted question description: https://leetcode.ca/all/1738.html
1738. Find Kth Largest XOR Coordinate Value
Level
Medium
Description
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 k-th
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] <= 10^6
1 <= k <= m * n
Solution
First, calculate the values of all coordinates of the matrix. To do this, first calculate each row’s prefix XOR results. To calculate the value of coordinate (a, b)
, if a == 0
, then the value is simply the prefix XOR of coordinate (a, b)
. Otherwise, the value is the XOR result of the value of coordinate (a - 1, b)
and the prefix XOR of coordinate (a, b)
.
Next, use a priority queue to store the top k
XOR values. Loop over all values of the matrix and update the priority queue.
Finally, return the k
-th largest XOR coordinate value from the priority queue.
class Solution {
public int kthLargestValue(int[][] matrix, int k) {
int rows = matrix.length, columns = matrix[0].length;
int[][] rowXORs = new int[rows][columns];
for (int i = 0; i < rows; i++) {
rowXORs[i][0] = matrix[i][0];
for (int j = 1; j < columns; j++)
rowXORs[i][j] = rowXORs[i][j - 1] ^ matrix[i][j];
}
int[][] totalXORs = new int[rows][columns];
for (int j = 0; j < columns; j++)
totalXORs[0][j] = rowXORs[0][j];
for (int i = 1; i < rows; i++) {
for (int j = 0; j < columns; j++)
totalXORs[i][j] = totalXORs[i - 1][j] ^ rowXORs[i][j];
}
PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>();
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
priorityQueue.offer(totalXORs[i][j]);
if (priorityQueue.size() > k)
priorityQueue.poll();
}
}
return priorityQueue.poll();
}
}