Leetcode 1738. Find Kth Largest XOR Coordinate Value

Explanation

We are given a 2D matrix with non-negative integers and an integer k. We will have to find the kth largest value of XOR in the matrix. XOR is calculated as (a, b) coordinate where 0 <= i <= a < m and 0 <= j <= b < n (0-indexed).

To solve this problem, we can iterate over the matrix and calculate the XOR values for all coordinates. After calculating each XOR value, we can push it into a priority queue with a custom comparator to keep track of the kth largest value. Finally, after traversing the matrix, the top element of the priority queue will be our answer.

Example

Let's walk through an example to understand the algorithm better.

Given matrix: [[5,2],[1,6]] and k = 3.

1. Initialize an auxiliary matrix called xors with dimensions (m + 1) x (n + 1) and a minHeap with the greater<>() as the comparator.
2. Iterate over the matrix:

• Calculate the XOR values for each coordinate: (5 XOR 2), (5 XOR 1), and (5 XOR 2 XOR 1 XOR 6).
• Push these values into the minHeap: after iterating the matrix, the minHeap will be [0, 4, 5, 7].
• If the size of the minHeap is greater than k, pop the smallest value to maintain the minHeap size as k.

3. After the loop, the top element of the minHeap is the 3rd largest XOR value, which is 4.

Solution

Python

1import heapq
2
3class Solution:
4    def kthLargestValue(self, matrix, k):
5        m, n = len(matrix), len(matrix[0])
6        xors = [[0] * (n + 1) for _ in range(m + 1)]
7        minHeap = []
8
9        for i in range(1, m+1):
10            for j in range(1, n+1):
11                xors[i][j] = xors[i-1][j] ^ xors[i][j-1] ^ xors[i-1][j-1] ^ matrix[i-1][j-1]
12                heapq.heappush(minHeap, xors[i][j])
13                if len(minHeap) > k:
14                    heapq.heappop(minHeap)
15
16        return heapq.heappop(minHeap)

Java

1import java.util.PriorityQueue;
2
3class Solution {
4    public int kthLargestValue(int[][] matrix, int k) {
5        int m = matrix.length, n = matrix[0].length;
6        int[][] xors = new int[m+1][n+1];
7        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
8
9        for (int i = 1; i <= m; i++) {
10            for (int j = 1; j <= n; j++) {
11                xors[i][j] = xors[i-1][j] ^ xors[i][j-1] ^ xors[i-1][j-1] ^ matrix[i-1][j-1];
12                minHeap.offer(xors[i][j]);
13                if (minHeap.size() > k)
14                    minHeap.poll();
15            }
16        }
17
18        return minHeap.poll();
19    }
20}

JavaScript

1class Solution {
2    kthLargestValue(matrix, k) {
3        const m = matrix.length;
4        const n = matrix[0].length;
5        const xors = Array.from({length:m+1}, () => new Array(n+1).fill(0));
6        const minHeap = [];
7
8        for (let i = 1; i <= m; i++) {
9            for (let j = 1; j <= n; j++) {
10                xors[i][j] = xors[i-1][j] ^ xors[i][j-1] ^ xors[i-1][j-1] ^ matrix[i-1][j-1];
11                minHeap.push(xors[i][j]);
12                
13                minHeap.sort((a, b) => a - b);
14                
15                if (minHeap.length > k)
16                    minHeap.shift();
17            }
18        }
19
20        return minHeap.shift();
21    }
22};

C++

1#include <vector>
2#include <queue>
3
4class Solution {
5 public:
6  int kthLargestValue(std::vector<std::vector<int>>& matrix, int k) {
7    const int m = matrix.size();
8    const int n = matrix[0].size();
9    std::vector<std::vector<int>> xors(m + 1, std::vector<int>(n + 1));
10    std::priority_queue<int, std::vector<int>, std::greater<>> minHeap;
11
12    for (int i = 1; i <= m; ++i) {
13      for (int j = 1; j <= n; ++j) {
14        xors[i][j] = xors[i - 1][j] ^ xors[i][j - 1] ^ xors[i - 1][j - 1] ^
15                     matrix[i - 1][j - 1];
16        minHeap.push(xors[i][j]);
17        if (minHeap.size() > k)
18          minHeap.pop();
19      }
20    }
21
22    return minHeap.top();
23  }
24};

C#

1using System;
2using System.Collections.Generic;
3
4public class Solution {
5    public int KthLargestValue(int[][] matrix, int k) {
6        int m = matrix.Length, n = matrix[0].Length;
7        int[][] xors = new int[m+1][];
8        for (int i = 0; i <= m; i++)
9            xors[i] = new int[n+1];
10        
11        SortedSet<Tuple<int,int>> minHeap = new SortedSet<Tuple<int,int>>(Comparer<Tuple<int,int>>.Create((a, b) => a.Item1 == b.Item1 ? a.Item2.CompareTo(b.Item2) : a.Item1.CompareTo(b.Item1)));
12        int count = 0;
13        
14        for (int i = 1; i <= m; i++) {
15            for (int j = 1; j <= n; j++) {
16                xors[i][j] = xors[i-1][j] ^ xors[i][j-1] ^ xors[i-1][j-1] ^ matrix[i-1][j-1];
17                minHeap.Add(new Tuple<int,int>(xors[i][j], count++));
18                if (minHeap.Count > k)
19                    minHeap.Remove(minHeap.Min);
20            }
21        }
22        
23        return minHeap.Min.Item1;
24    }
25}

Please note that these solutions use different standard libraries respective of each language, such as heapq for Python, PriorityQueue and SortedSet for Java and C#, and Arrays for JavaScript.

In summary, to solve this problem, we create an auxiliary XOR matrix, calculate the XOR value for each coordinate, and push the XOR values to a min-heap with a custom comparator to retain the kth largest value. After iterating through the matrix, the top element in the min-heap is the solution to the problem. The presented solutions cover Python, JavaScript, Java, C++, and C# programming languages.