Watch 10 video solutions for Path With Minimum Effort, a medium level problem involving Array, Binary Search, Depth-First Search. This walkthrough by take U forward has 259,458 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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) (i.e., 0-indexed). 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.
Example 1:
Input: heights = [[1,2,2],[3,8,2],[5,3,5]] Output: 2 Explanation: The route of [1,3,5,3,5] has a maximum absolute difference of 2 in consecutive cells. This is better than the route of [1,2,2,2,5], where the maximum absolute difference is 3.
Example 2:
Input: heights = [[1,2,3],[3,8,4],[5,3,5]] Output: 1 Explanation: The route of [1,2,3,4,5] has a maximum absolute difference of 1 in consecutive cells, which is better than route [1,3,5,3,5].
Example 3:
Input: heights = [[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]] Output: 0 Explanation: This route does not require any effort.
Constraints:
rows == heights.lengthcolumns == heights[i].length1 <= rows, columns <= 1001 <= heights[i][j] <= 106Problem Overview: You are given a grid of heights. Moving between adjacent cells costs the absolute height difference. The effort of a path is defined as the maximum difference between consecutive cells along that path. The task is to reach the bottom‑right cell while minimizing this maximum effort.
Approach 1: Dijkstra's Algorithm with Min Heap (O(mn log(mn)) time, O(mn) space)
This problem behaves like a shortest path problem on a grid graph. Each cell is a node and edges connect the four neighbors. Instead of summing weights, the path cost is the max difference seen so far. Use a min heap (priority queue) to always expand the cell with the smallest current effort. Maintain a matrix where dist[r][c] stores the minimum effort required to reach that cell. For each neighbor, compute newEffort = max(currentEffort, abs(heightDiff)). If this value is smaller than the recorded effort, update it and push the neighbor into the heap. This is the most direct and commonly accepted solution in interviews because it mirrors standard shortest path logic.
Approach 2: Binary Search + BFS Feasibility Check (O(mn log C) time, O(mn) space)
The key observation is that the answer lies between 0 and the maximum possible height difference. If you guess an effort value x, you can check whether a path exists where every step difference is ≤ x. This turns the problem into a reachability check using Breadth‑First Search. Perform binary search over the effort range. For each mid value, run BFS from the start and only traverse edges whose height difference is ≤ mid. If the bottom‑right cell is reachable, try a smaller effort; otherwise increase the limit. This approach separates optimization (binary search) from feasibility (graph traversal).
Recommended for interviews: Dijkstra's algorithm is usually the expected solution because the grid can be treated as a weighted graph and the logic directly minimizes path cost. It demonstrates strong understanding of graph shortest‑path patterns with a priority queue. The binary search + BFS approach is also solid and shows the ability to convert an optimization problem into a decision problem.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dijkstra's Algorithm with Min Heap | O(mn log(mn)) | O(mn) | General case. Best when treating the grid as a weighted graph and minimizing maximum edge cost. |
| Binary Search + BFS | O(mn log C) | O(mn) | Useful when you can convert the optimization into a feasibility check on the effort limit. |