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.
1var minimumEffortPath = function(heights) {
2 function canReachEnd(mid, heights, rows, cols) {
3 const queue = [[0, 0]];
4 const visited = Array.from({ length: rows }, () => Array(cols).fill(false));
5 visited[0][0] = true;
6 const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
7
8 while (queue.length) {
9 const [x, y] = queue.shift();
10 if (x === rows - 1 && y === cols - 1) return true;
11 for (const [dx, dy] of directions) {
12 const nx = x + dx, ny = y + dy;
13 if (nx >= 0 && ny >= 0 && nx < rows && ny < cols && !visited[nx][ny]) {
14 if (Math.abs(heights[nx][ny] - heights[x][y]) <= mid) {
15 queue.push([nx, ny]);
16 visited[nx][ny] = true;
17 }
18 }
19 }
20 }
21
22 return false;
23 }
24 const rows = heights.length;
25 const cols = heights[0].length;
26 let left = 0;
27 let right = 1e6;
28 let result = 0;
29
30 while (left <= right) {
31 const mid = Math.floor((left + right) / 2);
32 if (canReachEnd(mid, heights, rows, cols)) {
33 result = mid;
34 right = mid - 1;
35 } else {
36 left = mid + 1;
37 }
38 }
39
40 return result;
41};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.