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:


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);
        }        
    }
}