Scale Engineer

Find Kth Largest XOR Coordinate Value

Med
#1592Time: 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.
Patterns
Bit ManipulationPrefix Sum
Algorithms
Divide and ConquerSortingQuickselect
Data structures
ArrayHeap (Priority Queue)Matrix

Prompt

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

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 i from 1 to m and j from 1 to n:
    • 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 the values list.
  • Sort the values list 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 * n elements, 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.

Solutions

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

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.

← Previous

Previous problem

Next →

Next problem