Find Kth Largest XOR Coordinate Value
MedPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach first calculates all the coordinate values using a dynamic programming technique and then finds the k-th largest value by sorting all the calculated values.
Algorithm
- Initialize an
(m+1) x (n+1)DP table,prefixXor, with all zeros. - Initialize an empty list,
values, to store all coordinate values. - Iterate
ifrom 1 tomandjfrom 1 ton:- Calculate
prefixXor[i][j] = prefixXor[i-1][j] ^ prefixXor[i][j-1] ^ prefixXor[i-1][j-1] ^ matrix[i-1][j-1]. - Add
prefixXor[i][j]to thevalueslist.
- Calculate
- Sort the
valueslist in ascending order. - Return the element at index
values.size() - k.
Walkthrough
The core idea is to efficiently compute the value for each coordinate (r, c), which is the XOR sum of all elements in the rectangle from (0, 0) to (r, c). This can be viewed as a 2D prefix XOR problem. We can define dp[r][c] as the value of coordinate (r, c). The value dp[r][c] can be calculated using the values of its neighbors and the element matrix[r][c]. The recurrence relation is:
dp[r][c] = dp[r-1][c] ^ dp[r][c-1] ^ dp[r-1][c-1] ^ matrix[r][c].
(Here, ^ denotes the XOR operation).
We can create a DP table of size (m+1) x (n+1) to store these prefix XORs. We iterate through the matrix, compute each dp[i][j], and store all m * n computed values into a list. After populating the list with all coordinate values, we sort the list in ascending order. The k-th largest element will be at index list.size() - k.
import java.util.ArrayList;import java.util.Collections;import java.util.List; class Solution { public int kthLargestValue(int[][] matrix, int k) { int m = matrix.length; int n = matrix[0].length; int[][] prefixXor = new int[m + 1][n + 1]; List<Integer> values = new ArrayList<>(); for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { prefixXor[i][j] = prefixXor[i - 1][j] ^ prefixXor[i][j - 1] ^ prefixXor[i - 1][j - 1] ^ matrix[i - 1][j - 1]; values.add(prefixXor[i][j]); } } Collections.sort(values); return values.get(values.size() - k); }}Complexity
Time
O(m * n * log(m * n)). `O(m * n)` to compute all prefix XOR values. `O(m * n * log(m * n))` to sort the list of `m * n` values. The sorting step dominates the overall time complexity.
Space
O(m * n). We need `O(m * n)` space for the `prefixXor` DP table and another `O(m * n)` for the `values` list.
Trade-offs
Pros
Relatively simple to understand and implement.
Cons
The time complexity is high due to sorting all
m * nelements, which can be inefficient for large matrices.The space complexity is also high, requiring storage for both the DP table and the list of values.
This approach improves upon the first one by avoiding a full sort. Instead of storing all values and then sorting, we use a min-heap (Priority Queue) of size k to keep track of the k largest values seen so far.
Algorithm
- Initialize a min-heap,
minHeap. - Initialize an
(m+1) x (n+1)DP table,prefixXor, with all zeros. - Iterate
ifrom 1 tomandjfrom 1 ton:- Calculate the current coordinate's value:
currentValue = prefixXor[i-1][j] ^ prefixXor[i][j-1] ^ prefixXor[i-1][j-1] ^ matrix[i-1][j-1]. - Add
currentValuetominHeap. - If
minHeap.size() > k, callminHeap.poll().
- Calculate the current coordinate's value:
- Return
minHeap.peek().
Walkthrough
Similar to the first approach, we calculate the prefix XOR value for each coordinate. We maintain a min-heap of size k. As we calculate each coordinate's value, we add it to the heap. If the heap's size exceeds k, we remove the smallest element (the root of the min-heap). This ensures the heap always contains the k largest values encountered up to that point. After iterating through all coordinates, the root of the heap will be the k-th largest value overall. While the DP calculation can be done with O(m*n) space, it can also be optimized to use O(n) space, making this approach very memory-efficient.
import java.util.PriorityQueue; class Solution { public int kthLargestValue(int[][] matrix, int k) { int m = matrix.length; int n = matrix[0].length; // Min-heap to store the k largest values PriorityQueue<Integer> minHeap = new PriorityQueue<>(); int[][] prefixXor = new int[m + 1][n + 1]; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { prefixXor[i][j] = prefixXor[i - 1][j] ^ prefixXor[i][j - 1] ^ prefixXor[i - 1][j - 1] ^ matrix[i - 1][j - 1]; minHeap.offer(prefixXor[i][j]); if (minHeap.size() > k) { minHeap.poll(); } } } return minHeap.peek(); }}Complexity
Time
O(m * n * log k). `O(m * n)` to iterate through all coordinates and calculate their values. For each of the `m * n` values, we perform a heap operation (`offer` and possibly `poll`), which takes `O(log k)` time.
Space
O(m*n + k). `O(m * n)` for the `prefixXor` DP table and `O(k)` for the min-heap. Note: The DP calculation can be space-optimized to `O(n)`, leading to an overall space complexity of `O(n + k)`.
Trade-offs
Pros
More time-efficient than full sorting, especially when
kis much smaller thanm * n.Can be implemented with very good space efficiency (
O(n + k)) by optimizing the DP calculation.
Cons
Slightly more complex to implement than the sorting approach.
Time complexity is dependent on
log k, which can be close tolog(m*n)ifkis large.
This is the most time-efficient approach on average. It combines the O(m*n) dynamic programming calculation of coordinate values with the Quickselect algorithm, which finds the k-th largest element in linear average time.
Algorithm
- Initialize an
(m+1) x (n+1)DP table,prefixXor, with all zeros. - Initialize an empty list,
values, to store all coordinate values. - Iterate
ifrom 1 tomandjfrom 1 ton:- Calculate
prefixXor[i][j] = prefixXor[i-1][j] ^ prefixXor[i][j-1] ^ prefixXor[i-1][j-1] ^ matrix[i-1][j-1]. - Add
prefixXor[i][j]to thevalueslist.
- Calculate
- Use the Quickselect algorithm to find the
k-th largest element invalues. This is equivalent to finding the(N - k)-th smallest element, whereN = m * n. - Return the result from Quickselect.
Walkthrough
First, we compute all m * n coordinate values using the same DP technique as in the previous approaches and store them in a list or an array. Once we have the list of all values, we apply the Quickselect algorithm. Quickselect is a selection algorithm that modifies the Quicksort algorithm to find the k-th smallest (or largest) element in an unsorted list. It works by partitioning the array around a pivot element and recursively searching only in the partition that is expected to contain the k-th element. This avoids sorting the entire array. On average, Quickselect has a time complexity of O(N), where N is the number of elements (m * n in our case).
import java.util.ArrayList;import java.util.List;import java.util.Random; class Solution { public int kthLargestValue(int[][] matrix, int k) { int m = matrix.length; int n = matrix[0].length; int[][] prefixXor = new int[m + 1][n + 1]; List<Integer> values = new ArrayList<>(); for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { prefixXor[i][j] = prefixXor[i - 1][j] ^ prefixXor[i][j - 1] ^ prefixXor[i - 1][j - 1] ^ matrix[i - 1][j - 1]; values.add(prefixXor[i][j]); } } return quickSelect(values, k); } private int quickSelect(List<Integer> nums, int k) { int left = 0, right = nums.size() - 1; // k-th largest is (n-k)-th smallest int targetIndex = nums.size() - k; Random rand = new Random(); while (left <= right) { int pivotIndex = rand.nextInt(right - left + 1) + left; int finalPivotIndex = partition(nums, left, right, pivotIndex); if (finalPivotIndex == targetIndex) { return nums.get(finalPivotIndex); } else if (finalPivotIndex < targetIndex) { left = finalPivotIndex + 1; } else { right = finalPivotIndex - 1; } } return -1; // Should not happen } private int partition(List<Integer> nums, int left, int right, int pivotIndex) { int pivotValue = nums.get(pivotIndex); swap(nums, pivotIndex, right); // Move pivot to end int storeIndex = left; for (int i = left; i < right; i++) { if (nums.get(i) < pivotValue) { swap(nums, storeIndex, i); storeIndex++; } } swap(nums, storeIndex, right); // Move pivot to its final place return storeIndex; } private void swap(List<Integer> nums, int i, int j) { int temp = nums.get(i); nums.set(i, nums.get(j)); nums.set(j, temp); }}Complexity
Time
O(m * n) on average. `O(m * n)` to compute all prefix XOR values. `O(m * n)` on average for the Quickselect algorithm. The worst-case is `O((m*n)^2)`, but it's highly unlikely with a randomized pivot.
Space
O(m * n). `O(m * n)` for the `prefixXor` DP table and the `values` list. Even with a space-optimized DP calculation, we still need `O(m*n)` space to store all values for the Quickselect algorithm.
Trade-offs
Pros
Asymptotically the fastest approach on average.
Cons
Implementation of Quickselect is more complex than using built-in sorting or a priority queue.
Has a quadratic worst-case time complexity, although this is rare in practice with a good pivot strategy.
Requires
O(m*n)space to hold all values, which is less memory-efficient than the optimized min-heap approach.
Solutions
Solution
class Solution { public int kthLargestValue ( int [][] matrix , int k ) { int m = matrix . length , n = matrix [ 0 ]. length ; int [][] s = new int [ m + 1 ][ n + 1 ]; List < Integer > ans = new ArrayList <>(); 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 . add ( s [ i + 1 ][ j + 1 ]); } } Collections . sort ( ans ); return ans . get ( ans . size () - k ); } }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 ]; } };class Solution : def kthLargestValue ( self , matrix : List [ List [ int ]], k : int ) -> int : m , n = len ( matrix ), len ( matrix [ 0 ]) s = [[ 0 ] * ( n + 1 ) for _ in range ( m + 1 )] ans = [] for i in range ( m ): for j in range ( n ): s [ i + 1 ][ j + 1 ] = s [ i + 1 ][ j ] ^ s [ i ][ j + 1 ] ^ s [ i ][ j ] ^ matrix [ i ][ j ] ans . append ( s [ i + 1 ][ j + 1 ]) return nlargest ( k , ans )[ - 1 ]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.