Path With Minimum Effort - Solution & Explanation
Problem Statement
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] <= 106
Approach Overview
Problem 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 1: Dijkstra's Algorithm for Minimum Effort Path
In this approach, the grid cells are treated as nodes in a graph. The goal is to find the path from the top-left to the bottom-right with the minimum maximum effort. Dijkstra's algorithm is well-suited for finding the shortest path in graphs with non-negative weights, which aligns well with our need to minimize the maximum effort. We use a priority queue to process nodes with the smallest effort first, and update the effort required to reach each node as we explore the grid.
This Python solution uses Dijkstra's algorithm with a min-heap to efficiently find the minimum-effort path through the grid. We maintain a 2D array 'effort' where effort[x][y] stores the minimum effort required to reach the cell (x, y). The heap ensures we always process the cell with the lowest current effort next. Whenever a neighboring cell can be reached with less effort than previously recorded, we update and push it back into the heap.
Complexity
Time Complexity: O(N * log(N)), where N is the number of cells. This is due to processing each cell in the heap.
Space Complexity: O(N), for storing the effort values and the heap.
Approach 2: Binary Search with BFS
This approach combines binary search with a graph traversal method like BFS. The key idea is to use binary search to determine the minimum effort needed to traverse the grid by repeatedly checking if a path exists with a given effort threshold. The BFS part checks if it's possible to reach the destination without exceeding the current effort guess. By adjusting our search range based on the feasibility of the current 'mid' effort, we efficiently identify the minimum effort required.
This Java solution employs binary search over possible effort values. For each midpoint 'mid' of the binary search, we execute a BFS (breadth-first search) to verify if a path exists that does not exceed the current 'mid' effort. We adjust our search range (left, right) based on whether a valid path was found, honing in on the minimum possible effort.
Code
Java
JavaScript
Complexity
Time Complexity: O(Edges * log(max)), where max is the maximum possible height difference.
Space Complexity: O(N), for the BFS traversal and visited tracking.
Approach 3: Union-Find
For this problem, we can treat each cell as a node in a graph, and the absolute difference in height between two adjacent cells as the weight of the edge. Therefore, this problem is to solve the connectivity problem from the top-left node to the bottom-right node.
We first construct a set of edges, then sort them in ascending order of edge weight, and add edges one by one until the top-left node and the bottom-right node are connected. At this point, the weight of the edge is the minimum physical consumption value required by the problem.
The time complexity is O(m times n times log(m times n)), and the space complexity is O(m times n). Here, m and n are the number of rows and columns in the two-dimensional array, respectively.
Code
Python
Java
C++
Go
TypeScript
Approach 4: Binary Search + BFS
We notice that if the maximum physical consumption value of a path is x, then for any y > x, this path also meets the conditions. This shows monotonicity, so we can use the binary search method to find the minimum physical consumption value that meets the conditions.
We define the left boundary of the binary search as l=0, and the right boundary as r=10^6. Each time we take mid=(l+r)/2, then use BFS to determine whether there is a path from the top-left corner to the bottom-right corner, so that the absolute difference in height between adjacent nodes on the path is not greater than mid. If it exists, it means that mid may still be the minimum physical consumption value that meets the conditions, so we set r=mid, otherwise we set l=mid+1.
The time complexity is O(m times n times log M), and the space complexity is O(m times n). Here, m and n are the number of rows and columns in the two-dimensional array, respectively, and M is the maximum value in the two-dimensional array. In this problem, M=10^6.
Code
Python
Java
C++
Go
TypeScript
Approach 5: Heap-optimized Dijkstra Algorithm
We can treat each cell as a node in a graph, and the absolute difference in height between two adjacent cells as the weight of the edge. Therefore, this problem is to solve the shortest path problem from the top-left node to the bottom-right node.
We can use the Dijkstra algorithm to solve the shortest path problem, and use a priority queue (heap) to optimize the time complexity. Specifically, we maintain a two-dimensional array dist of size m times n, where dist[i][j] represents the maximum weight of the shortest path from the top-left corner to the node (i,j). Initially, dist[0][0]=0, and all other elements are positive infinity.
We use a priority queue (heap) to store nodes, and each time we take out the node with the smallest weight from the priority queue (heap), then update the weights of its adjacent nodes. If the weight of an adjacent node changes, then we add this node to the priority queue (heap). When the priority queue (heap) is empty, it means that we have found the shortest path.
The time complexity is O(m times n times log(m times n)), and the space complexity is O(m times n). Here, m and n are the number of rows and columns in the two-dimensional array, respectively.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dijkstra's Algorithm for Minimum Effort Path | Time Complexity: O(N * log(N)), where N is the number of cells. This is due to processing each cell in the heap. |
| Binary Search with BFS | Time Complexity: O(Edges * log(max)), where max is the maximum possible height difference. |
| Union-Find | — |
| Binary Search + BFS | — |
| Heap-optimized Dijkstra Algorithm | — |
Detailed Complexity Analysis
| 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. |
Video Solution
G-37. Path With Minimum Effort • take U forward • 286,220 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Path With Minimum Effort easy or hard?
How to solve Path With Minimum Effort in O(n)?
What is the best approach for Path With Minimum Effort?
Is Path With Minimum Effort asked at Google/Amazon/Meta?
What data structure is used in Path With Minimum Effort?
What is the time complexity of Path With Minimum Effort?
Path With Minimum Effort Python or Java solution approach?
Ready to solve this problem?
Practice Path With Minimum Effort with our built-in code editor and test cases.
Practice on FleetCode