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