Kth smallest element in a sorted matrix

Array Binary Search Sorting Heap (Priority Queue) Matrix

64.4% acceptance

Jan 12, 2026

10523

393

Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the kth smallest element in the matrix. Note that it is the kth smallest element in the sorted order, not the kth distinct element. You must find a solution with a memory complexity better than O(n2).

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn kth_smallest(matrix: Vec<Vec<i32>>, k: i32) -> i32 {
    let n = matrix.len();
    let mut left = matrix[0][0];
    let mut right = matrix[n - 1][n - 1];
    
    while left < right {
      let mid = left + (right - left) / 2;
      let count = Self::count_less_equal(&matrix, mid);
      
      if count < k {
        left = mid + 1;
      } else {
        right = mid;
      }
    }
    
    left
  }
  
  fn count_less_equal(matrix: &Vec<Vec<i32>>, target: i32) -> i32 {
    let n = matrix.len();
    let mut count = 0;
    let mut col = n - 1;
    
    for row in 0..n {
      while col > 0 && matrix[row][col] > target {
        col -= 1;
      }
      if matrix[row][col] <= target {
        count += col + 1;
      }
    }
    
    count as i32
  }
}