Find Kth Largest XOR Coordinate Value

MEDIUM

Description

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 k^th 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] <= 10⁶
1 <= k <= m * n

Approaches

Checkout 3 different approaches to solve Find Kth Largest XOR Coordinate Value. Click on different approaches to view the approach and algorithm in detail.

Dynamic Programming with Sorting

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.

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 Analysis

Time Complexity: 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 Complexity: O(m * n). We need `O(m * n)` space for the `prefixXor` DP table and another `O(m * n)` for the `values` list.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Find Kth Largest XOR Coordinate Value. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Find Kth Largest XOR Coordinate Value

Algorithms:

Divide and ConquerSortingQuickselect

Patterns:

Bit ManipulationPrefix Sum

Data Structures:

ArrayHeap (Priority Queue)Matrix