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 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.
C++
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.
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.
JavaScript
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 | 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. |
G-37. Path With Minimum Effort • take U forward • 178,287 views views
Watch 9 more video solutions →Practice Path With Minimum Effort with our built-in code editor and test cases.
Practice on FleetCode