1738. Find Kth Largest XOR Coordinate Value LeetCode Solution

In this guide, you will get 1738. Find Kth Largest XOR Coordinate Value LeetCode Solution with the best time and space complexity. The solution to Find Kth Largest XOR Coordinate Value problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Find Kth Largest XOR Coordinate Value solution in C++
4. Find Kth Largest XOR Coordinate Value solution in Java
5. Find Kth Largest XOR Coordinate Value solution in Python
6. Additional Resources

Problem Statement of 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.

Constraints:

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

Complexity Analysis

• Time Complexity: O(mn\log k)
• Space Complexity: O(mn + k)

1738. Find Kth Largest XOR Coordinate Value LeetCode Solution in C++

class Solution {
 public:
  int kthLargestValue(vector<vector<int>>& matrix, int k) {
    const int m = matrix.size();
    const int n = matrix[0].size();
    vector<vector<int>> xors(m + 1, vector<int>(n + 1));
    priority_queue<int, vector<int>, greater<>> minHeap;

    for (int i = 1; i <= m; ++i)
      for (int j = 1; j <= n; ++j) {
        xors[i][j] = xors[i - 1][j] ^ xors[i][j - 1] ^ xors[i - 1][j - 1] ^
                     matrix[i - 1][j - 1];
        minHeap.push(xors[i][j]);
        if (minHeap.size() > k)
          minHeap.pop();
      }

    return minHeap.top();
  }
};
/* code provided by PROGIEZ */

1738. Find Kth Largest XOR Coordinate Value LeetCode Solution in Java

class Solution {
  public int kthLargestValue(int[][] matrix, int k) {
    final int m = matrix.length;
    final int n = matrix[0].length;
    int[][] xors = new int[m + 1][n + 1];
    Queue<Integer> minHeap = new PriorityQueue<>();

    for (int i = 1; i <= m; ++i)
      for (int j = 1; j <= n; ++j) {
        xors[i][j] = xors[i - 1][j] ^ xors[i][j - 1] ^ xors[i - 1][j - 1] ^ matrix[i - 1][j - 1];
        minHeap.offer(xors[i][j]);
        if (minHeap.size() > k)
          minHeap.poll();
      }

    return minHeap.peek();
  }
}
// code provided by PROGIEZ

1738. Find Kth Largest XOR Coordinate Value LeetCode Solution in Python

N/A
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.