DSA interview question

Path with Minimum Effort

Hard · Data structures · Topics: graph, dijkstra, matrix

The problem

A hiker plans a route across a grid of terrain heights from the top-left to the bottom-right cell, moving 4-directionally. A route's effort is its largest single step (the maximum absolute height difference between consecutive cells), since that's what exhausts the hiker. Find the route with the minimum effort. This is a shortest-path problem where a path's cost is the maximum edge on it instead of the sum. Dijkstra still works: settle cells in order of their best-known effort, and relax with max(effort so far, step).

Example: [[1,2,2], [3,8,2], [5,3,5]] → 2.

Function signature

int minimumEffortPath(const vector<vector<int>>& heights);

Test cases

Input	Output	Explanation
`[[1,2,2],[3,8,2],[5,3,5]]`	`2`	The route 1-3-5-3-5
`[[1,2,3],[3,8,4],[5,3,5]]`	`1`	Along the top and right edges
`[[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]`	`0`	A snake through equal heights
`[[1,10]]`	`9`	One unavoidable step
`[[5]]`	`0`	Already at the goal

(Confirm: 4-directional moves; effort is the maximum absolute difference along the path.)

How interviewers phrase it

"Return the minimum effort required to travel from the top-left cell to the bottom-right cell, where a route's effort is the maximum absolute difference in heights between two consecutive cells of the route" (LeetCode 1631).

Clarifying questions to ask

4-directional? (Yes.)
Is effort the maximum step or the sum of steps? (The maximum.)
Sizes and heights? (100 × 100 cells, heights up to 10⁶.)

Follow-ups to expect

"Why does Dijkstra still work with max?"
"Binary search alternative?"
"Union-find alternative?"
"Can you stop early?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview