Path With Minimum Effort
Problem Description
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
Solve it on LeetCode
Approaches
1. DFS with Backtracking
The simplest solution is to use Depth-First Search (DFS) to explore all possible paths. For each path, we calculate the maximum effort and keep track of the minimum effort path found. The algorithm explores all paths and can thus guarantee that it finds the minimum effort path.
Intuition:
- Use DFS to explore paths from the top-left to the bottom-right.
- Record the efforts in each path and maintain the minimum path effort found.
- Use backtracking to ensure all possible paths are explored.
Code:
- Time Complexity: O((M*N)!): In the worst case, each cell tries all paths.
- Space Complexity: O(M * N): Space for visited matrix.
2. Binary Search with BFS
We can optimize the approach by using binary search along with a BFS for path verification. The key idea is that the minimum effort path must lie within a specific range, and this range can be narrowed down using binary search.
Intuition:
- Perform a binary search on the range of effort to find the minimum possible effort.
- For each mid effort, use BFS to check if there exists a valid path from start to end.
Code:
- Time Complexity: O(log(max_height) * M * N): Binary search combined with BFS check over the matrix.
- Space Complexity: O(M * N): Space for visited matrix and queue.
3. Dijkstra's Algorithm with Min-Heap
The most efficient approach is to use a modified version of Dijkstra's algorithm to keep track of the minimum effort distance via a priority queue (min-heap).
Intuition:
- Treat each cell as a node and update efforts using min-heap.
- Always expand the node with the smallest effort difference until reaching the bottom-right cell.
Code:
- Time Complexity: O(M * N * log(M * N)): Each cell is processed via the priority queue which maintains its order logarithmically.
- Space Complexity: O(M * N): To keep track of efforts to reach each cell.