Path with minimum effort

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

62.8% acceptance

Feb 25, 2026

6782

237

You are a hiker preparing for an upcoming hike. You are given heights, a 2D array of size rows x columns, where heights[row][col] represents the height of cell (row, col). You are situated in the top-left cell, (0, 0), and you hope to travel to the bottom-right cell, (rows-1, columns-1). You can move up, down, left, or right, and you wish to find a route that requires the minimum effort. A route's effort is the maximum absolute difference in heights between two consecutive cells of the route. Return the minimum effort required to travel from the top-left cell to the bottom-right cell.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

use std::collections::BinaryHeap;
use std::cmp::Reverse;

impl Solution {
  pub fn minimum_effort_path(heights: Vec<Vec<i32>>) -> i32 {
    let rows = heights.len();
    let cols = heights[0].len();
    let mut dist = vec![vec![i32::MAX; cols]; rows];
    dist[0][0] = 0;
    let mut heap = BinaryHeap::new();
    heap.push(Reverse((0, 0, 0)));
    let dirs = [(0i32, 1i32), (0, -1), (1, 0), (-1, 0)];
    while let Some(Reverse((effort, r, c))) = heap.pop() {
      if r == rows - 1 && c == cols - 1 { return effort; }
      if effort > dist[r][c] { continue; }
      for (dr, dc) in dirs {
        let nr = r as i32 + dr;
        let nc = c as i32 + dc;
        if nr < 0 || nr >= rows as i32 || nc < 0 || nc >= cols as i32 { continue; }
        let nr = nr as usize;
        let nc = nc as usize;
        let new_effort = effort.max((heights[r][c] - heights[nr][nc]).abs());
        if new_effort < dist[nr][nc] {
          dist[nr][nc] = new_effort;
          heap.push(Reverse((new_effort, nr, nc)));
        }
      }
    }
    0
  }
}