Path with maximum minimum value

Array Binary Search Depth-First Search Breadth-First Search Union-Find Heap (Priority Queue) Matrix

54.6% acceptance

Mar 31, 2026

1355

126

Given an m x n integer matrix grid, return the maximum score of a path starting at (0, 0) and ending at (m - 1, n - 1) moving in the 4 cardinal directions. The score of a path is the minimum value in that path. For example, the score of the path 8 → 4 → 5 → 9 is 4.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_minimum_path(grid: Vec<Vec<i32>>) -> i32 {
    use std::collections::BinaryHeap;
    let m = grid.len();
    let n = grid[0].len();
    let mut visited = vec![vec![false; n]; m];
    // Max-heap of (min_val_on_path, row, col)
    let mut heap = BinaryHeap::new();
    heap.push((grid[0][0], 0usize, 0usize));
    visited[0][0] = true;
    let dirs = [(0i32, 1i32), (0, -1), (1, 0), (-1, 0)];
    while let Some((val, r, c)) = heap.pop() {
      if r == m - 1 && c == n - 1 {
        return val;
      }
      for &(dr, dc) in &dirs {
        let nr = r as i32 + dr;
        let nc = c as i32 + dc;
        if nr >= 0 && nr < m as i32 && nc >= 0 && nc < n as i32 {
          let (nr, nc) = (nr as usize, nc as usize);
          if !visited[nr][nc] {
            visited[nr][nc] = true;
            heap.push((val.min(grid[nr][nc]), nr, nc));
          }
        }
      }
    }
    -1
  }
}