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
Rust Solution
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);
}
Having problems with this solution? Click here to submit an issue on github.