Loading problems...
TL;DR: The optimal solution treats the grid as a weighted graph and uses a modified Dijkstra's algorithm to find the path that minimizes the maximum absolute difference between adjacent cells.
The Path With Minimum Effort problem asks us to navigate a 2D grid of heights from the top-left cell (0, 0) to the bottom-right cell (rows-1, columns-1). We can move in the four cardinal directions (up, down, left, right). The "effort" of a path is defined as the maximum absolute difference in height between any two consecutive cells in that path. Our objective is to find a route where this maximum absolute difference is minimized.
This is a classic variation of the shortest path problem found in LeetCode 1631, where the "cost" function is a minimax value rather than a cumulative sum.
The naive approach involves exploring every possible simple path from the source to the destination to calculate their respective efforts, then choosing the minimum among them. This is typically implemented using Depth-First Search (DFS) with backtracking.
Pseudo-code:
text
function dfs(row, col, current_max_diff, visited):
if (row, col) is destination:
return current_max_diff
mark (row, col) as visited
min_effort = infinity
for each neighbor (r, c):
if (r, c) not visited:
diff = abs(heights[row][col] - heights[r][c])
new_max = max(current_max_diff, diff)
result = dfs(r, c, new_max, visited)
min_effort = min(min_effort, result)
unmark (row, col)
return min_effortTime Complexity:
In the worst case, the recursion explores an exponential number of paths. For a grid of size , this is computationally infeasible.
Why it fails: The brute force method fails due to Time Limit Exceeded (TLE). The constraints allow for a grid size up to , resulting in 10,000 cells. Enumerating all paths in such a dense graph is impossible within standard time limits. We need an approach that polynomially finds the optimal path without traversing all possibilities.
The key intuition for solving LeetCode 1631 efficiently lies in adapting the relaxation condition of Dijkstra's Algorithm.
In a standard Dijkstra implementation, we maintain the minimum cumulative distance to reach a node. Here, we maintain the minimum effort required to reach a node. The "effort" to reach a neighbor v from node u is not effort[u] + weight(u, v), but rather max(effort[u], weight(u, v)). This is because the path's cost is determined solely by the largest height difference encountered so far.
The algorithm maintains a strict invariant: at any point, the Priority Queue provides the reachable node with the lowest possible "maximum effort" discovered. By always expanding the path with the minimal "bottleneck" (the smallest maximum difference), we guarantee that when we reach the destination, we have found the path with the global minimum effort.
Visual Description: Imagine the grid as a network of nodes.
(0,0) with a known effort of 0. All other nodes are initialized to infinity.(0, 0) into a Min-Priority Queue.max(current_effort, |height_diff|)) that is smaller than the neighbor's previously recorded effort, we update the neighbor's value and add it to the queue.
We implement Dijkstra's algorithm using a Min-Priority Queue and a 2D distance matrix (often named effort or dist).
dist[r][c] store the minimum effort required to travel from (0, 0) to (r, c). Initialize all values to infinity (∞), except dist[0][0], which is 0.(current_effort, row, col). This ensures we always process the cell reachable with the least effort first.(0, 0, 0) onto the Min-Heap.(d, r, c).d > dist[r][c], this is an outdated entry; skip it.(r, c) is the bottom-right cell, return d.(nr, nc).weight = abs(heights[r][c] - heights[nr][nc]).new_effort = max(d, weight).new_effort < dist[nr][nc]:
dist[nr][nc] = new_effort.(new_effort, nr, nc) to the Min-Heap.Let's trace the logic for a small example.
Input: heights = [[1, 2], [3, 8]]
Init:
dist matrix: [[0, ∞], [∞, ∞]][(0, 0, 0)] (effort, row, col)Step 1:
(0, 0, 0). Current cell is (0, 0) with height 1.abs(1 - 2) = 1.max(0, 1) = 1.1 < ∞, so update dist[0][1] = 1. Push (1, 0, 1).abs(1 - 3) = 2.max(0, 2) = 2.2 < ∞, so update dist[1][0] = 2. Push (2, 1, 0).[(1, 0, 1), (2, 1, 0)]Step 2:
(1, 0, 1). Current cell is (0, 1) with height 2.abs(2 - 8) = 6.max(1, 6) = 6.6 < ∞, so update dist[1][1] = 6. Push (6, 1, 1).[(2, 1, 0), (6, 1, 1)]Step 3:
(2, 1, 0). Current cell is (1, 0) with height 3.abs(3 - 8) = 5.max(2, 5) = 5.5 < 6 (current value in dist[1][1]), so update dist[1][1] = 5. Push (5, 1, 1).[(5, 1, 1), (6, 1, 1)] (Note: the old entry (6,1,1) remains but will be skipped later).Step 4:
(5, 1, 1). Current cell is target (1, 1).5.The algorithm is correct because it satisfies the greedy choice property and optimal substructure of Dijkstra's algorithm.
We are looking for a path that minimizes the function . When we extract a node with effort from the priority queue, we claim that is the optimal (minimum) effort to reach . Suppose there existed another path to with effort . This path must leave the set of visited nodes at some boundary node currently in the priority queue. However, the effort of any path through would be at least the effort to reach . Since the priority queue yields the minimum value, the effort to reach must be . Since edge weights are non-negative, extending the path cannot decrease the maximum absolute difference. Thus, is indeed minimal.
cpp#include <vector> #include <queue> #include <cmath> #include <algorithm> using namespace std; class Solution { public: int minimumEffortPath(vector<vector<int>>& heights) { int rows = heights.size(); int cols = heights[0].size(); // Min-priority queue to store {effort, row, col} // Ordered by effort ascending priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq; // Distance matrix to track min effort to reach each cell // Initialize with a large value vector<vector<int>> dist(rows, vector<int>(cols, 1e9)); dist[0][0] = 0; pq.push({0, 0, 0}); int dr[] = {0, 0, 1, -1}; int dc[] = {1, -1, 0, 0}; while (!pq.empty()) { auto current = pq.top(); pq.pop(); int currentEffort = current[0]; int r = current[1]; int c = current[2]; // If we reached the bottom-right cell, return the effort if (r == rows - 1 && c == cols - 1) { return currentEffort; } // If we found a shorter path to this cell already, skip if (currentEffort > dist[r][c]) continue; // Check all 4 directions for (int i = 0; i < 4; i++) { int nr = r + dr[i]; int nc = c + dc[i]; if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) { int weight = abs(heights[r][c] - heights[nr][nc]); int newEffort = max(currentEffort, weight); // If this path offers a lower max-effort, update and push if (newEffort < dist[nr][nc]) { dist[nr][nc] = newEffort; pq.push({newEffort, nr, nc}); } } } } return 0; // Should not reach here } };
javaimport java.util.PriorityQueue; import java.util.Arrays; class Solution { public int minimumEffortPath(int[][] heights) { int rows = heights.length; int cols = heights[0].length; // Priority Queue stores arrays: {effort, row, col} // Orders by effort ascending PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]); // dist[r][c] stores the minimum effort to reach (r, c) int[][] dist = new int[rows][cols]; for (int[] row : dist) { Arrays.fill(row, Integer.MAX_VALUE); } dist[0][0] = 0; pq.offer(new int[]{0, 0, 0}); int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; while (!pq.isEmpty()) { int[] current = pq.poll(); int currentEffort = current[0]; int r = current[1]; int c = current[2]; if (r == rows - 1 && c == cols - 1) { return currentEffort; } // Optimization: Skip if we found a better path already if (currentEffort > dist[r][c]) continue; for (int[] dir : directions) { int nr = r + dir[0]; int nc = c + dir[1]; if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) { int weight = Math.abs(heights[r][c] - heights[nr][nc]); // Key logic: effort is the max absolute difference along the path int newEffort = Math.max(currentEffort, weight); if (newEffort < dist[nr][nc]) { dist[nr][nc] = newEffort; pq.offer(new int[]{newEffort, nr, nc}); } } } } return 0; } }
pythonimport heapq class Solution: def minimumEffortPath(self, heights: list[list[int]]) -> int: rows, cols = len(heights), len(heights[0]) # Priority Queue stores tuples: (effort, row, col) # Initialize with start node pq = [(0, 0, 0)] # dist matrix initialized to infinity dist = [[float('inf')] * cols for _ in range(rows)] dist[0][0] = 0 directions = [(0, 1), (0, -1), (1, 0), (-1, 0)] while pq: current_effort, r, c = heapq.heappop(pq) # If we reached the target, return result if r == rows - 1 and c == cols - 1: return current_effort # Skip if we found a better way to this cell if current_effort > dist[r][c]: continue for dr, dc in directions: nr, nc = r + dr, c + dc if 0 <= nr < rows and 0 <= nc < cols: weight = abs(heights[r][c] - heights[nr][nc]) new_effort = max(current_effort, weight) if new_effort < dist[nr][nc]: dist[nr][nc] = new_effort heapq.heappush(pq, (new_effort, nr, nc)) return 0
Let be the number of rows and be the number of columns. The total number of nodes (vertices) is . The total number of edges is (since each cell has at most 4 neighbors).
Time Complexity: Standard Dijkstra's runs in . Substituting our variables, we get , which simplifies to . This is highly efficient for the given constraints ().
Space Complexity:
We require space for the dist matrix to store the minimum effort for each cell. The priority queue can also store up to elements in the worst case.
The Dijkstra pattern used here is versatile. The key is identifying what constitutes the "cost" or "distance" and how to "relax" an edge.
new_prob = curr_prob * edge_prob.Q: Why does a standard BFS or DFS result in Time Limit Exceeded (TLE)?
Q: Why can't we just sum the differences like standard Dijkstra?
new_dist = dist[u] + weight.Q: Why do we need the if (currentEffort > dist[r][c]) continue; check?