Find kth largest xor coordinate value

Array Divide and Conquer Bit Manipulation Sorting Heap (Priority Queue) Matrix Prefix Sum Quickselect

64.2% acceptance

Feb 25, 2026

538

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.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn kth_largest_value(mut matrix: Vec<Vec<i32>>, k: i32) -> i32 {
    let m = matrix.len();
    let n = matrix[0].len();
    // Build XOR prefix sum in-place
    for i in 0..m {
      for j in 0..n {
        if i > 0 { matrix[i][j] ^= matrix[i-1][j]; }
        if j > 0 { matrix[i][j] ^= matrix[i][j-1]; }
        if i > 0 && j > 0 { matrix[i][j] ^= matrix[i-1][j-1]; }
      }
    }
    // Collect all values and find kth largest
    let mut vals: Vec<i32> = matrix.into_iter().flatten().collect();
    vals.sort_unstable_by(|a, b| b.cmp(a));
    vals[k as usize - 1]
  }
}