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] <= 106In #1631 Path With Minimum Effort, the goal is to move from the top-left to the bottom-right of a grid while minimizing the maximum height difference between consecutive cells along the path. Instead of minimizing total cost, we minimize the largest edge cost encountered.
A common approach is Dijkstra’s algorithm with a priority_queue. Treat each cell as a node, and the edge weight between neighbors as the absolute height difference. The distance for a node represents the minimum possible maximum effort needed to reach it. Using a min-heap ensures we always expand the cell with the currently smallest effort.
Another effective technique is Binary Search + BFS/DFS. We binary search the answer (maximum allowed effort) and check if the destination is reachable using only edges with difference ≤ the chosen threshold.
Both strategies rely on graph traversal over the matrix. Dijkstra directly computes the optimal effort, while binary search turns the problem into repeated reachability checks.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dijkstra with Priority Queue | O(m * n log(m * n)) | O(m * n) |
| Binary Search + BFS/DFS | O(m * n log(MaxHeight)) | O(m * n) |
take U forward
Use these hints if you're stuck. Try solving on your own first.
Consider the grid as a graph, where adjacent cells have an edge with cost of the difference between the cells.
If you are given threshold k, check if it is possible to go from (0, 0) to (n-1, m-1) using only edges of ≤ k cost.
Binary search the k value.
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.
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.
1#include <vector>
2#include <queue>
3#include <cmath>
4#include <limits>
5
6using namespace std;
7
8int minimumEffortPath(vector<vector<int>>& heights) {
9 int rows = heights.size();
10 int cols = heights[0].size();
11 vector<vector<int>> effort(rows, vector<int>(cols, numeric_limits<int>::max()));
12 effort[0][0] = 0;
13 priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;
14 pq.push({0, 0, 0});
15 vector<pair<int, int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
16
17 while (!pq.empty()) {
18 auto [current_effort, x, y] = pq.top();
19 pq.pop();
20 if (x == rows - 1 && y == cols - 1) return current_effort;
21 for (auto &[dx, dy] : directions) {
22 int nx = x + dx, ny = y + dy;
23 if (nx >= 0 && ny >= 0 && nx < rows && ny < cols) {
24 int new_effort = max(current_effort, abs(heights[nx][ny] - heights[x][y]));
25 if (new_effort < effort[nx][ny]) {
26 effort[nx][ny] = new_effort;
27 pq.push({new_effort, nx, ny});
28 }
29 }
30 }
31 }
32 return 0;
33}This C++ solution implements the same logic as the Python version using Dijkstra's algorithm with a priority queue. The priority queue stores a tuple of (current_effort, x, y) to facilitate processing the smallest effort first. Each cell's effort is updated if we find a path with less effort than previously known.
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.
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.
1var minimumEffortPath = function(heights)
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem is a popular interview question because it tests graph traversal, heap usage, and binary search on the answer. It also checks a candidate’s ability to model grid problems as graphs.
A priority queue (min-heap) is ideal when using Dijkstra’s algorithm because it efficiently selects the next cell with the smallest effort. For the binary search approach, a queue or stack is used for BFS or DFS traversal.
A common optimal approach is Dijkstra’s algorithm using a priority queue. Each grid cell is treated as a node, and the cost is the maximum height difference encountered so far. This ensures we always expand the path with the currently smallest effort.
Yes. You can binary search the minimum possible effort and check reachability using BFS or DFS. For each candidate effort, you only traverse edges whose height difference is within that limit.
This JavaScript solution mirrors the logic of the Java implementation, using a binary search to find the minimum effort. For each midpoint, a BFS is used to check if reaching the bottom-right corner is feasible with the current effort, adjusting the search window as needed.