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

All Problems

All Solutions