Compile Ready
Module 6 · Shortest Path

Path With Minimum Effort

MediumProblem 21 of 25 11 min read ~35 min to solve LeetCode
GraphShortest PathDijkstraBinary SearchBFSHeapMatrix
Asked atAmazonGoogleMicrosoftMetaAppleUber

Problem Statement

You are given a rectangular grid heights. You start at the top-left cell and want to reach the bottom-right cell. You may move 4-directionally.

The effort of a path is the maximum absolute height difference between two consecutive cells on that path. Return the minimum possible effort over all valid paths.

Input

A 2D integer grid heights where each value is the height of that cell.

Output

An integer: the smallest possible maximum edge difference along any path from top-left to bottom-right.

Constraints

  • •rows == heights.length
  • •cols == heights[i].length
  • •1 <= rows, cols <= 100
  • •1 <= heights[i][j] <= 1000000
  • •Movement is 4-directional only.

Examples

Example 1

Input: 
heights = [[1,2,2],[3,8,2],[5,3,5]]
Output: 2
Explanation: A path can avoid the steep jump to 8. The best route has edge differences at most 2, and no route can keep every step below 2.

Example 2

Input: 
heights = [[1,2,3],[3,8,4],[5,3,5]]
Output: 1
Explanation: There is a path whose every consecutive height difference is at most 1.

Example 3

Input: 
heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
Output: 0
Explanation: A route exists through only cells of height 1, so the maximum step difference is 0.

Learning Objectives

  • Distinguish additive path cost from bottleneck path cost.
  • Adapt Dijkstra by changing the relaxation formula from sum to max.
  • Use binary search on the answer when feasibility is monotonic.
  • Recognise that both shortest-path and threshold-reachability views can solve the same problem optimally.

Intuition

The path score is not the sum of all climbs. A long gentle route can be better than a short route with one huge jump because the only thing that matters is the worst single edge on the path.

Dijkstra still works if you redefine what distance means. Instead of dist[cell] being the minimum total cost to reach the cell, let it be the minimum possible maximum edge difference seen so far. When moving to a neighbour, the candidate effort is max(current effort, edge difference). If that candidate improves the neighbour, relax it. The same greedy proof applies: when the smallest effort state is popped, no later path can reach it with a smaller maximum edge because all future candidates are at least as large as the popped key.

There is also a powerful alternative. Ask: if I allow only steps with difference at most x, can I reach the target? If yes for x, then yes for any larger limit. If no for x, then no for any smaller limit. That monotonic yes/no property lets us binary search the answer and run BFS or DFS as the feasibility check.

Dijkstra usually has the better interview flow because it returns the exact answer in one pass. Binary search plus BFS is excellent when you spot a monotonic threshold and want a reusable decision-problem pattern.

Common mistakes

  • ×Summing height differences instead of minimising the maximum difference.
  • ×Using plain BFS without considering effort values; edges have different effective costs.
  • ×Marking a cell visited once globally before its best effort is known. Dijkstra should skip stale states using the effort matrix.
  • ×Allowing diagonal moves. The problem is 4-directional only.
  • ×In binary search, forgetting to reset the visited matrix for each feasibility check.

Algorithm Explanation

Dijkstra-style bottleneck path: effort[r][c] is the best known maximum edge difference needed to reach that cell. Start with effort[0][0] = 0. Pop the cell with smallest effort from a min-heap. For each 4-directional neighbour, compute candidate = max(current effort, absolute height difference). If candidate improves the neighbour, update and push it. The first time the target is popped, return its effort.

Binary search + BFS feasibility: effort limits are monotonic. For a proposed limit mid, run BFS using only edges whose height difference is at most mid. If the target is reachable, try a smaller limit; otherwise try a larger one. The final low value is the minimum feasible effort.

Dijkstra is a direct one-pass shortest-path adaptation. Binary search separates optimisation from reachability and is useful when the answer range is small or the feasibility test is easier than deriving a custom relaxation.

Solutions

Solution 1: Dijkstra with max-edge relaxation

When to prefer this:

Use this as the primary solution. It is a true shortest-path algorithm over a bottleneck cost and avoids the extra logarithmic factor over the height range.

Store the best effort known for every cell. The relaxation from a cell to a neighbour takes the maximum of the current path effort and the new edge difference. The heap always expands the currently easiest cell to reach.

Step-by-step

  1. Initialise all efforts to infinity and effort[0][0] = 0.
  2. Push the start into a min-heap ordered by effort.
  3. Pop the smallest effort state and skip it if stale.
  4. If it is the target, return the effort immediately.
  5. For each 4-directional neighbour, compute max(current effort, abs height difference).
  6. If that candidate improves the neighbour, store it and push a new heap state.
Time

O(rows · cols · log(rows · cols))

Space

O(rows · cols)

Each cell can be improved and pushed into the heap; stale entries are skipped.

Java implementation

Loading…

Solution 2: Binary search on effort with BFS

When to prefer this:

Use this when you notice the monotonic threshold property quickly or when explaining optimisation via feasibility checks. It is slightly less direct but very reusable.

For a candidate effort limit, ignore every edge whose height difference is larger than the limit. A BFS then answers whether top-left can reach bottom-right. Because reachability only becomes easier as the limit grows, binary search finds the smallest feasible limit.

Step-by-step

  1. Binary search low = 0 and high = 1000000, the maximum possible height gap.
  2. For mid, run canReach(mid).
  3. canReach performs BFS from the start and only crosses edges with difference <= mid.
  4. If target is reachable, mid is feasible, so move high down.
  5. Otherwise mid is too small, so move low up.
  6. When low == high, it is the minimum effort.
Time

O(rows · cols · log C)

Space

O(rows · cols)

C is the height range, at most 1000000. Each feasibility check is one BFS.

Java implementation

Loading…

Dry Run

Sample input

Dijkstra trace for heights = [[1,2,2],[3,8,2],[5,3,5]].

StepHeap popNeighbour relaxationsBest efforts changedReason
1(0 effort, 0,0)(0,1) edge 1; (1,0) edge 2(0,1)=1, (1,0)=2Start has no effort yet
2(1 effort, 0,1)(0,2) max 1; (1,1) max 6(0,2)=1, (1,1)=6The jump to 8 is expensive
3(1 effort, 0,2)(1,2) edge 0 keeps effort 1(1,2)=1Flat move stays cheap
4(1 effort, 1,2)(2,2) edge 3 gives effort 3(2,2)=3Target found but not final until popped
5(2 effort, 1,0)(2,0) max 2(2,0)=2A different route keeps bottleneck 2
6(2 effort, 2,0)(2,1) max 2(2,1)=2Route around the 8 improves path
7(2 effort, 2,1)(2,2) max 2 improves 3(2,2)=2Target effort lowered
8(2 effort, 2,2)target poppedanswer 2Smallest possible effort is settled

The first route to the target has effort 3, but Dijkstra does not stop when a target is merely discovered. It stops when the target is popped with the smallest unsettled effort, which happens at 2.

Interview Tips

Start by saying this is a bottleneck shortest path, not an additive shortest path. That phrase tells the interviewer you understand the twist. Then present Dijkstra with max(current, edge) relaxation. If time permits, add the binary-search view: a threshold x is feasible if BFS can reach the target using only edges of size at most x. Contrasting these two approaches is a strong Senior-level signal because it shows both algorithm adaptation and monotonic reasoning.

Likely follow-ups

  • Return one minimum-effort path. Store parent coordinates whenever effort improves.
  • Solve with Union-Find by sorting edges by difference and connecting cells until start and target share a component.
  • What if movement included diagonals? Extend the direction array and keep the same algorithms.
  • What if the path score were the sum of differences instead? Use ordinary Dijkstra with additive relaxation.

Similar Problems

Network Delay Time
MediumStandard Dijkstra with additive edge weights.
Cheapest Flights Within K Stops
MediumAnother weighted shortest-path problem where state and path cost need care.
Shortest Path in Binary Matrix
MediumUnweighted grid shortest path; compare BFS with weighted-grid Dijkstra.
Swim in Rising Water
HardVery similar bottleneck path structure with time as the threshold.

Key Takeaways

  • Not every path cost is a sum; this problem minimises the maximum edge on the path.
  • Dijkstra can be adapted when the relaxation preserves a monotonic best-known key.
  • Binary search works because reachability under an effort limit is monotonic.
  • Do not stop when the target is first discovered in Dijkstra; stop when it is popped as the best unsettled state.
Reusable template: Bottleneck path: relax neighbours with max(current path cost, edge cost), or binary search the allowed edge threshold and test reachability.