Find Kth Largest XOR Coordinate Value solution and explanation
Google
9 more videos on this problem
Find Kth Largest XOR Coordinate Value | leetcode 1738 | Contest 225 Question 3Coding Decoded · 8:57 · 1K views
LeetCode 1738. Find Kth Largest XOR Coordinate Value | Visualization | PythonAH Tech · 6:18 · 629 views
Leetcode 1738. Find Kth Largest XOR Coordinate ValueFraz · 26:16 · 618 views
1738. Find Kth Largest XOR Coordinate Value (Leetcode Medium)Programming Live with Larry · 9:35 · 397 views
【每日一题】1738. Find Kth Largest XOR Coordinate Value, 3/18/2021Huifeng Guan · 18:41 · 303 views
1738. Find Kth Largest XOR Coordinate ValueShuo Yan · 10:47 · 53 views
Leetcode 1738. Find Kth Largest XOR Coordinate Value (2d prefix sum)LetsCode · 9:33 · 45 views
LeetCode 1738: Find Kth Largest XOR Coordinate ValueAlitaCode · 33:56 · 22 views
1738. Find Kth Largest XOR Coordinate Value - C++ (DP, Heap, Priority Queue, Bit Manipulation)Leetcode w dropout PhD · 14:18 · 5 views
LeetCode 1738. Find Kth Largest XOR Coordinate ValueyoBro · 0:22 · 3 views
The problem
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.lengthn == matrix[i].length1 <= m, n <= 10000 <= matrix[i][j] <= 1061 <= k <= m * n
Approach overview
Problem Overview: You are given an m x n matrix. For every coordinate (i, j), compute the XOR of all elements in the submatrix from (0,0) to (i,j). This value is called the XOR coordinate value. After computing all m*n values, return the kth largest among them.
The core challenge is efficiently computing XOR values for every submatrix. Recomputing each region from scratch would be expensive, so the key idea is to reuse previously computed results using a prefix sum-style technique with XOR.
Approach 1: Prefix XOR + Min-Heap (O(mn log k) time, O(k) space)
Compute the XOR prefix for each cell using the relation px[i][j] = matrix[i][j] ^ px[i-1][j] ^ px[i][j-1] ^ px[i-1][j-1]. This works similarly to a 2D prefix sum but uses XOR operations. While iterating through the matrix, push each prefix XOR value into a min-heap of size k. If the heap grows beyond k, remove the smallest element. This keeps only the k largest XOR values seen so far, and the heap root becomes the answer.
The insight is that you do not need to store or sort all m*n values. A heap (priority queue) maintains the top k elements efficiently. Each matrix cell is processed once, making the traversal O(mn), while heap updates cost O(log k).
Approach 2: Prefix XOR + Sorting (O(mn log(mn)) time, O(mn) space)
First compute all XOR coordinate values using the same 2D prefix XOR formula. Store every computed value in an array. After processing the entire matrix, sort the array in descending order and return the element at index k-1.
This approach is straightforward and easy to implement. However, sorting all m*n values adds extra overhead compared to maintaining only the top k. For large matrices, O(mn log(mn)) becomes noticeably slower than the heap-based solution. Still, it remains a good option when code simplicity is preferred or when k is close to m*n.
Recommended for interviews: The prefix XOR with min-heap solution is typically expected. Interviewers want to see that you recognize the 2D prefix XOR pattern (a variant of prefix sum) and combine it with a priority queue to maintain the kth largest element efficiently. The sorting approach demonstrates understanding of the prefix XOR computation, but the heap solution shows stronger optimization skills.
Approach 1: Prefix XOR and Min-Heap
We can use prefix XOR to quickly calculate the XOR value of any sub-matrix. The prefix XOR at (i, j) can be defined as the XOR of all elements from (0, 0) to (i, j). With this, the XOR for every coordinate can be derived quickly. To find the kth largest value among these, a min-heap of size k can be used, continually maintaining the largest k values observed so far.
import heapq
def kthLargestValue(matrix, k):
m, n = len(matrix), len(matrix[0])
xor_matrix = [[0] * (n + 1) for _ in range(m + 1)]
min_heap = []
for i in range(1, m + 1):
for j in range(1, n + 1):
xor_matrix[i][j] = matrix[i-1][j-1] ^ xor_matrix[i-1][j] ^ xor_matrix[i][j-1] ^ xor_matrix[i-1][j-1]
heapq.heappush(min_heap, xor_matrix[i][j])
if len(min_heap) > k:
heapq.heappop(min_heap)
return min_heap[0]import java.util.PriorityQueue;
public int kthLargestValue(int[][] matrix, int k) {
int m = matrix.length, n = matrix[0].length;
int[][] xorMatrix = new int[m + 1][n + 1];
PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
xorMatrix[i][j] = matrix[i - 1][j - 1] ^ xorMatrix[i - 1][j] ^ xorMatrix[i][j - 1] ^ xorMatrix[i - 1][j - 1];
minHeap.offer(xorMatrix[i][j]);
if (minHeap.size() > k) {
minHeap.poll();
}
}
}
return minHeap.peek();
}This Python solution uses a min-heap to track the kth largest XOR value. We compute the prefix XOR for each element in the matrix, storing each result in the heap. If the heap exceeds size k, we remove the smallest item. Our final result is the smallest item in this size-k heap, which represents the kth largest XOR value.
Time Complexity: O(m * n * log k), where m is the number of rows and n is the number of columns.
Space Complexity: O(m * n + k).
Approach 2: Prefix XOR and Sorting
An alternative approach is to calculate all possible XOR values using prefix XOR and then sort these values to directly find the kth largest. Although this method might have higher time complexity due to sorting, it is straightforward and utilizes built-in sorting algorithms for reliability.
function kthLargestValue(matrix, k) {
const m = matrix.length, n = matrix[0].length;
const xorMatrix = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
const values = [];
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
xorMatrix[i][j] = matrix[i - 1][j - 1] ^ xorMatrix[i - 1][j] ^ xorMatrix[i][j - 1] ^ xorMatrix[i - 1][j - 1];
values.push(xorMatrix[i][j]);
}
}
values.sort((a, b) => b - a);
return values[k - 1];
}#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
return *(int*)b - *(int*)a;
}
int kthLargestValue(int** matrix, int matrixSize, int* matrixColSize, int k) {
int m = matrixSize, n = matrixColSize[0];
int* values = (int*)malloc((m * n) * sizeof(int));
int** xorMatrix = (int**)malloc((m + 1) * sizeof(int*));
for(int i = 0; i <= m; i++) {
xorMatrix[i] = (int*)calloc((n + 1), sizeof(int));
}
int idx = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
xorMatrix[i][j] = matrix[i - 1][j - 1] ^ xorMatrix[i - 1][j] ^ xorMatrix[i][j - 1] ^ xorMatrix[i - 1][j - 1];
values[idx++] = xorMatrix[i][j];
}
}
qsort(values, m * n, sizeof(int), cmp);
int result = values[k - 1];
free(values);
for (int i = 0; i <= m; i++) {
free(xorMatrix[i]);
}
free(xorMatrix);
return result;
}The JavaScript solution follows a similar pattern to the C implementation. It calculates all possible XOR values, stores them in an array, and sorts this array to determine the kth largest value. The built-in sort method helps to efficiently organize the results.
Time Complexity: O(m * n log(m * n)), because of sorting the XOR values.
Space Complexity: O(m * n) for storing XOR values.
Approach 3: Two-dimensional Prefix XOR + Sorting or Quick Selection
We define a two-dimensional prefix XOR array s, where s[i][j] represents the XOR result of the elements in the first i rows and the first j columns of the matrix, i.e.,
$
s[i][j] = \bigoplus_{0 leq x leq i, 0 leq y leq j} matrix[x][y]
And s[i][j] can be calculated from the three elements s[i - 1][j], s[i][j - 1] and s[i - 1][j - 1], i.e.,
s[i][j] = s[i - 1][j] \oplus s[i][j - 1] \oplus s[i - 1][j - 1] \oplus matrix[i - 1][j - 1]
We traverse the matrix, calculate all s[i][j], then sort them, and finally return the kth largest element. If you don't want to use sorting, you can also use the quick selection algorithm, which can optimize the time complexity.
The time complexity is O(m times n times log (m times n)) or O(m times n), and the space complexity is O(m times n). Here, m and n$ are the number of rows and columns of the matrix, respectively.
class Solution {
public:
int kthLargestValue(vector<vector<int>>& matrix, int k) {
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> s(m + 1, vector<int>(n + 1));
vector<int> ans;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
s[i + 1][j + 1] = s[i + 1][j] ^ s[i][j + 1] ^ s[i][j] ^ matrix[i][j];
ans.push_back(s[i + 1][j + 1]);
}
}
sort(ans.begin(), ans.end());
return ans[ans.size() - k];
}
};function kthLargestValue(matrix: number[][], k: number): number {
const m: number = matrix.length;
const n: number = matrix[0].length;
const s = Array.from({ length: m + 1 }, () => Array.from({ length: n + 1 }, () => 0));
const ans: number[] = [];
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
s[i + 1][j + 1] = s[i + 1][j] ^ s[i][j + 1] ^ s[i][j] ^ matrix[i][j];
ans.push(s[i + 1][j + 1]);
}
}
ans.sort((a, b) => b - a);
return ans[k - 1];
}func kthLargestValue(matrix [][]int, k int) int {
m, n := len(matrix), len(matrix[0])
s := make([][]int, m+1)
for i := range s {
s[i] = make([]int, n+1)
}
var ans []int
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
s[i+1][j+1] = s[i+1][j] ^ s[i][j+1] ^ s[i][j] ^ matrix[i][j]
ans = append(ans, s[i+1][j+1])
}
}
sort.Ints(ans)
return ans[len(ans)-k]
}Complexity comparison
| Approach | Complexity |
|---|---|
| Prefix XOR and Min-Heap | Time Complexity: O(m * n * log k), where m is the number of rows and n is the number of columns. |
| Prefix XOR and Sorting | Time Complexity: O(m * n log(m * n)), because of sorting the XOR values. |
| Two-dimensional Prefix XOR + Sorting or Quick Selection | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix XOR + Min-Heap | O(mn log k) | O(k) | Best general solution when k is much smaller than m*n |
| Prefix XOR + Sorting | O(mn log(mn)) | O(mn) | Simple implementation when memory is not a concern |
Frequently asked questions
Is Find Kth Largest XOR Coordinate Value easy or hard?
The problem is rated Medium because it combines multiple concepts: 2D prefix XOR computation and selecting the kth largest value using a heap or sorting. Understanding the prefix XOR relation is the main challenge; once that is clear, the rest of the implementation is straightforward.
Find Kth Largest XOR Coordinate Value Python/Java solution
Python and Java implementations typically compute prefix XOR values while iterating through the matrix and push them into a priority queue of size k. Python uses heapq for the min-heap, while Java uses PriorityQueue. Both implementations achieve O(mn log k) time complexity.
How to solve Find Kth Largest XOR Coordinate Value in O(n)?
The matrix must be processed fully, so the lower bound is O(mn). Using a 2D prefix XOR allows computing each coordinate value in constant time after previous values are known. Maintaining a heap of size k keeps the total complexity at O(mn log k), which is the practical optimal solution.
What is the best approach for Find Kth Largest XOR Coordinate Value?
The most efficient approach uses a 2D prefix XOR combined with a min-heap. Compute the XOR value for each matrix coordinate using the prefix relation, then maintain a heap of size k containing the largest values seen so far. This reduces the complexity to O(mn log k) instead of sorting all m*n values.
Is Find Kth Largest XOR Coordinate Value asked at Google/Amazon/Meta?
This type of problem appears in interviews at companies that test matrix processing and prefix techniques, including Amazon and Google-style coding rounds. It evaluates understanding of prefix XOR, matrix traversal, and heap-based selection problems.
What data structure is used in Find Kth Largest XOR Coordinate Value?
The key structures are a 2D prefix XOR array and a min-heap (priority queue). The prefix array efficiently computes submatrix XOR values, while the heap keeps track of the top k largest results without storing or sorting every value.
What is the time complexity of Find Kth Largest XOR Coordinate Value?
The optimal solution runs in O(mn log k) time, where m and n are the matrix dimensions. Each cell contributes one prefix XOR computation and one heap operation. A simpler approach that stores all values and sorts them takes O(mn log(mn)) time.