Formatted question description: https://leetcode.ca/all/1738.html

# 1738. Find Kth Largest XOR Coordinate Value

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.length;
int[][] rowXORs = new int[rows][columns];
for (int i = 0; i < rows; i++) {
rowXORs[i] = matrix[i];
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[j] = rowXORs[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();
}
}