1738. 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.

Example 4:

Input: matrix = [[5,2],[1,6]], k = 4
Output: 0
Explanation: The value of coordinate (1,1) is 5 XOR 2 XOR 1 XOR 6 = 0, which is the 4th largest value.

 

Constraints:

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

1738. Find Kth Largest XOR Coordinate Value
struct Solution;

impl Solution {
    fn kth_largest_value(matrix: Vec<Vec<i32>>, k: i32) -> i32 {
        let n = matrix.len();
        let m = matrix[0].len();
        let k = k as usize;
        let mut xor = vec![vec![0; m]; n];
        xor[0][0] = matrix[0][0];
        let mut arr = vec![];
        for i in 1..n {
            xor[i][0] = xor[i - 1][0] ^ matrix[i][0];
        }
        for j in 1..m {
            xor[0][j] = xor[0][j - 1] ^ matrix[0][j];
        }
        for i in 1..n {
            for j in 1..m {
                xor[i][j] = xor[i - 1][j - 1] ^ xor[i][j - 1] ^ xor[i - 1][j] ^ matrix[i][j];
            }
        }
        for i in 0..n {
            for j in 0..m {
                arr.push(xor[i][j]);
            }
        }
        arr.select_nth_unstable(n * m - k);
        arr[n * m - k]
    }
}

#[test]
fn test() {
    let matrix = vec_vec_i32![[5, 2], [1, 6]];
    let k = 1;
    let res = 7;
    assert_eq!(Solution::kth_largest_value(matrix, k), res);
    let matrix = vec_vec_i32![[5, 2], [1, 6]];
    let k = 2;
    let res = 5;
    assert_eq!(Solution::kth_largest_value(matrix, k), res);
    let matrix = vec_vec_i32![[5, 2], [1, 6]];
    let k = 3;
    let res = 4;
    assert_eq!(Solution::kth_largest_value(matrix, k), res);
    let matrix = vec_vec_i32![[5, 2], [1, 6]];
    let k = 4;
    let res = 0;
    assert_eq!(Solution::kth_largest_value(matrix, k), res);
}