Median of a row wise sorted matrix

Array Binary Search Matrix

71.0% acceptance

Mar 31, 2026

Given an m x n matrix grid containing an odd number of integers where each row is sorted in non-decreasing order, return the median of the matrix. You must solve the problem in less than O(m * n) time complexity.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn matrix_median(grid: Vec<Vec<i32>>) -> i32 {
    let m = grid.len();
    let n = grid[0].len();
    let target = (m * n) / 2; // 0-indexed median position
    
    let mut lo = 1i32;
    let mut hi = 1_000_000i32;
    
    while lo < hi {
      let mid = lo + (hi - lo) / 2;
      // Count elements <= mid
      let mut count = 0usize;
      for row in &grid {
        // Binary search: number of elements <= mid
        count += row.partition_point(|&x| x <= mid);
      }
      if count <= target {
        lo = mid + 1;
      } else {
        hi = mid;
      }
    }
    
    lo
  }
}