1860. Find Kth Largest Xor Coordinate Value¶

Difficulty: Medium

1860. Find Kth Largest XOR Coordinate Value

Medium

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.

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 1000
0 <= matrix[i][j] <= 10⁶
1 <= k <= m * n

Solution¶

class Solution {
    private int pref[][];
    static class customSort implements Comparator<Integer> {
        @Override
        public int compare(Integer first, Integer second) {
            return Integer.compare(first, second);
        }
    }
    public int kthLargestValue(int[][] matrix, int k) {
        int n = matrix.length, m = matrix[0].length;        

        buildPref(matrix);

        PriorityQueue<Integer> pq = new PriorityQueue<>(new customSort());
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                pq.offer(pref[i][j]);
                if (pq.size() > k) 
                    pq.poll(); 
            }
        }
        return pq.poll();
    }
    private void buildPref(int arr[][]) {
        int n = arr.length, m = arr[0].length;
        pref = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i - 1 >= 0) 
                    pref[i][j] ^= pref[i - 1][j];
                if (j - 1 >= 0)
                    pref[i][j] ^= pref[i][j - 1];
                if (i - 1 >= 0 && j - 1 >= 0) 
                    pref[i][j] ^= pref[i - 1][j - 1];
                pref[i][j] ^= arr[i][j];
            }
        }
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here