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.
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.
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].
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.
rows == heights.length
columns == heights[i].length
1 <= rows, columns <= 100
1 <= heights[i][j] <= 106
Use binary search to search for minimum effort, within each binary search, use depth-first search to find if can find a path within the effort limit.
class Solution: def minimumEffortPath(self, heights: List[List[int]]) -> int: start = 0 end = 10000000 while start + 1 < end: mid = (start + end) // 2 if self.dfs(heights, set(), 0, 0, mid): end = mid else: start = mid if self.dfs(heights, set(), 0, 0, start): return start if self.dfs(heights, set(), 0, 0, end): return end return -1 def dfs(self, heights, visited, x, y, limit): if x == len(heights) - 1 and y == len(heights) - 1: return True visited.add((x, y)) DIRECTIONS = [(0, 1), (1, 0), (0, -1), (-1, 0)] for dx, dy in DIRECTIONS: next_x = x + dx next_y = y + dy if not self.is_valid(heights, next_x, next_y): continue if (next_x, next_y) in visited: continue if abs(heights[next_x][next_y] - heights[x][y]) > limit: continue if self.dfs(heights, visited, next_x, next_y, limit): return True return False def is_valid(self, heights, x, y): if not (0 <= x < len(heights) and 0 <= y < len(heights)): return False return True
- Time Complexity: O(MN), where M is the number of rows of the matrix, N is the number of columns of the matrix.
- Space Complexity: O(MN).