Graphs/Path With Minimum EffortMedium

This practice workspace is built for desktop. Open it on a larger screen to start solving.

Path With Minimum Effort

Graphs·Medium

You are given an m x n matrix heights of integers representing the heights of cells. A route's effort is the maximum absolute difference in heights between any two consecutive cells along the path. Return the minimum effort of a path from the top-left cell (0, 0) to the bottom-right cell (m-1, n-1).

Use Dijkstra's algorithm on the grid: maintain a 2-D distance array effort[r][c] (the minimum worst-case effort to reach (r, c)). For each cell, relax its four neighbors by considering max(current_effort, |heights[r][c] - heights[nr][nc]|).

Examples

Input: heights = [[1,2,2],[3,8,2],[5,3,5]]

Output: 2

Path [1,3,5,3,5] has effort max(2,2,2,2)=2, which is optimal.

Input: heights = [[1,2,3],[3,8,4],[5,3,5]]

Output: 1

Path [1,2,3,4,5] has maximum absolute difference 1.

Constraints

m == heights.length
n == heights[i].length
1 <= m, n <= 100
1 <= heights[i][j] <= 10^6

00:00Preview Mode (Read Only)

Loading editor…

Tests

Preview Mode

This is a read-only preview of DSAMind's AI coaching. Sign up to get custom feedback on your own solution.

Passed32 ms

First attempt — retry to track metric movement here.

Your approach

Pattern:Graphs
Time:O(N)
Space:O(1)

Complete approach — pattern and complexity both named.

Coach

What you got right

You correctly matched the sorted input requirement and implemented a linear-time scan using two pointers.

Where it diverged

No divergence detected. The code correctly aligns with the stated approach.

Next attempt: focus on

Try solving related sliding window problems to build familiarity with two-pointer variants.

Signals

No signals fired — clean run, you stayed in flow.