# 1631. Path With Minimum Effort

• Time: $O(mn\log mn)$
• Space: $O(mn)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 struct T { int i; int j; int d; T(int i, int j, int d) : i(i), j(j), d(d) {} }; class Solution { public: int minimumEffortPath(vector>& heights) { const int m = heights.size(); const int n = heights[0].size(); const vector dirs{0, 1, 0, -1, 0}; auto compare = [](const T& a, const T& b) { return a.d > b.d; }; priority_queue, decltype(compare)> minHeap(compare); // diff[i][j] := max absolute difference to reach (i, j) vector> diff(m, vector(n, INT_MAX)); vector> seen(m, vector(n)); minHeap.emplace(0, 0, 0); diff[0][0] = 0; while (!minHeap.empty()) { const auto [i, j, d] = minHeap.top(); minHeap.pop(); if (i == m - 1 && j == n - 1) return d; seen[i][j] = true; for (int k = 0; k < 4; ++k) { const int x = i + dirs[k]; const int y = j + dirs[k + 1]; if (x < 0 || x == m || y < 0 || y == n) continue; if (seen[x][y]) continue; const int newDiff = abs(heights[i][j] - heights[x][y]); const int maxDiff = max(diff[i][j], newDiff); if (diff[x][y] > maxDiff) { diff[x][y] = maxDiff; minHeap.emplace(x, y, maxDiff); } } } throw; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 class T { public int i; public int j; public int d; // max difference of (i, j) and its neighbors public T(int i, int j, int d) { this.i = i; this.j = j; this.d = d; } } class Solution { public int minimumEffortPath(int[][] heights) { final int m = heights.length; final int n = heights[0].length; final int[] dirs = {0, 1, 0, -1, 0}; Queue minHeap = new PriorityQueue<>((a, b) -> a.d - b.d); // dist[i][j] := max absolute difference to reach (i, j) int[][] diff = new int[m][n]; Arrays.stream(diff).forEach(row -> Arrays.fill(row, Integer.MAX_VALUE)); boolean[][] seen = new boolean[m][n]; minHeap.offer(new T(0, 0, 0)); diff[0][0] = 0; while (!minHeap.isEmpty()) { final int i = minHeap.peek().i; final int j = minHeap.peek().j; final int d = minHeap.poll().d; if (i == m - 1 && j == n - 1) return d; seen[i][j] = true; for (int k = 0; k < 4; ++k) { final int x = i + dirs[k]; final int y = j + dirs[k + 1]; if (x < 0 || x == m || y < 0 || y == n) continue; if (seen[x][y]) continue; final int newDiff = Math.abs(heights[i][j] - heights[x][y]); final int maxDiff = Math.max(diff[i][j], newDiff); if (diff[x][y] > maxDiff) { diff[x][y] = maxDiff; minHeap.offer(new T(x, y, maxDiff)); } } } throw new IllegalArgumentException(); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class Solution: def minimumEffortPath(self, heights: List[List[int]]) -> int: m = len(heights) n = len(heights[0]) dirs = [0, 1, 0, -1, 0] # diff[i][j] := max absolute difference to reach (i, j diff = [[math.inf] * n for _ in range(m)] seen = set() minHeap = [(0, 0, 0)] # (d, i, j) diff[0][0] = 0 while minHeap: d, i, j = heapq.heappop(minHeap) if i == m - 1 and j == n - 1: return d seen.add((i, j)) for k in range(4): x = i + dirs[k] y = j + dirs[k + 1] if x < 0 or x == m or y < 0 or y == n: continue if (x, y) in seen: continue newDiff = abs(heights[i][j] - heights[x][y]) maxDiff = max(diff[i][j], newDiff) if diff[x][y] > maxDiff: diff[x][y] = maxDiff heapq.heappush(minHeap, (diff[x][y], x, y))