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.
1import heapq
2
3def minimumEffortPath(heights):
4 rows, cols = len(heights), len(heights[0])
5 directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
6 effort = [[float('inf')] * cols for _ in range(rows)]
7 effort[0][0] = 0
8 min_heap = [(0, 0, 0)] # (effort, row, col)
9
10 while min_heap:
11 current_effort, x, y = heapq.heappop(min_heap)
12 if x == rows - 1 and y == cols - 1:
13 return current_effort
14 for dx, dy in directions:
15 nx, ny = x + dx, y + dy
16 if 0 <= nx < rows and 0 <= ny < cols:
17 new_effort = max(current_effort, abs(heights[nx][ny] - heights[x][y]))
18 if new_effort < effort[nx][ny]:
19 effort[nx][ny] = new_effort
20 heapq.heappush(min_heap, (new_effort, nx, ny))
21 return 0This 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.
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.
1import java.util.LinkedList;
2import java.util.Queue;
3
4class Solution {
5 public int minimumEffortPath(int[][] heights) {
6 int rows = heights.length, cols = heights[0].length;
7 int left = 0, right = 1_000_000, answer = 0;
8 int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
9
10 while (left <= right) {
11 int mid = left + (right - left) / 2;
12 Queue<int[]> queue = new LinkedList<>();
13 boolean[][] visited = new boolean[rows][cols];
14 queue.offer(new int[]{0, 0});
15 visited[0][0] = true;
16
17 while (!queue.isEmpty()) {
18 int[] curr = queue.poll();
19 int x = curr[0], y = curr[1];
20 if (x == rows - 1 && y == cols - 1) {
21 answer = mid;
22 right = mid - 1;
23 break;
24 }
25 for (int[] dir : directions) {
26 int nx = x + dir[0], ny = y + dir[1];
27 if (nx >= 0 && ny >= 0 && nx < rows && ny < cols && !visited[nx][ny]) {
28 if (Math.abs(heights[nx][ny] - heights[x][y]) <= mid) {
29 visited[nx][ny] = true;
30 queue.offer(new int[]{nx, ny});
31 }
32 }
33 }
34 }
35 if (!visited[rows-1][cols-1]) left = mid + 1;
36 }
37 return answer;
38 }
39}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.