By Long Luo
This article is the solution 3 Approaches: BFS(Dijkstra), Binary Search, Union Find of Problem 1631. Path With Minimum Effort.
Here shows 3 Approaches to slove this problem: BFS(Dijkstra), Binary Search, Union Find.
BFS(Dijkstra)
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
| public int minimumEffortPath(int[][] heights) { if (heights == null || heights.length == 0 || heights[0].length == 0) { return 0; }
int rows = heights.length; int cols = heights[0].length;
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
PriorityQueue<int[]> pq = new PriorityQueue<>((edge1, edge2) -> edge1[2] - edge2[2]);
pq.offer(new int[]{0, 0, 0});
int[] dist = new int[rows * cols]; Arrays.fill(dist, Integer.MAX_VALUE);
dist[0] = 0;
boolean[][] vis = new boolean[rows][cols];
while (!pq.isEmpty()) { int[] edge = pq.poll();
int x = edge[0]; int y = edge[1]; int d = edge[2];
if (vis[x][y]) { continue; }
if (x == rows - 1 && y == cols - 1) { break; }
vis[x][y] = true; for (int[] dir : dirs) { int nextX = x + dir[0]; int nextY = y + dir[1];
if (nextX >= 0 && nextX < rows && nextY >= 0 && nextY < cols && Math.max(d, Math.abs(heights[nextX][nextY] - heights[x][y])) < dist[nextX * cols + nextY]) { dist[nextX * cols + nextY] = Math.max(d, Math.abs(heights[nextX][nextY] - heights[x][y])); pq.offer(new int[]{nextX, nextY, dist[nextX * cols + nextY]}); } } }
return dist[rows * cols - 1]; }
|
Analysis
- Time Complexity: \(O(mnlog(mn))\).
- Space Complexity: \(O(mn)\).
Binary Search
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
| public int minimumEffortPath(int[][] heights) { int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int rows = heights.length; int cols = heights[0].length;
int left = 0; int right = 1_000_000 - 1;
while (left < right) { int mid = left + (right - left) / 2;
boolean[][] visited = new boolean[rows][cols];
Queue<int[]> queue = new LinkedList<>(); queue.offer(new int[]{0, 0});
visited[0][0] = true;
while (!queue.isEmpty()) { int[] curPos = queue.poll(); for (int[] dir : dirs) { int nextX = curPos[0] + dir[0]; int nextY = curPos[1] + dir[1];
if (nextX >= 0 && nextX < rows && nextY >= 0 && nextY < cols && !visited[nextX][nextY] && Math.abs(heights[nextX][nextY] - heights[curPos[0]][curPos[1]]) <= mid) { visited[nextX][nextY] = true; queue.offer(new int[]{nextX, nextY}); } } }
if (visited[rows - 1][cols - 1]) { right = mid; } else { left = mid + 1; } }
return left; }
|
Analysis
- Time Complexity: \(O(mnlogC)\).
- Space Complexity: \(O(mn)\).
Union Find
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 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84
| public int minimumEffortPath(int[][] heights) { int rows = heights.length; int cols = heights[0].length;
List<int[]> edges = new ArrayList<>();
for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { int index = i * cols + j; if (i > 0) { edges.add(new int[]{index - cols, index, Math.abs(heights[i][j] - heights[i - 1][j])}); }
if (j > 0) { edges.add(new int[]{index - 1, index, Math.abs(heights[i][j] - heights[i][j - 1])}); } } }
Collections.sort(edges, (edge1, edge2) -> edge1[2] - edge2[2]);
UnionFind uf = new UnionFind(rows * cols); int ans = 0; for (int[] edge : edges) { int x = edge[0]; int y = edge[1]; int d = edge[2]; uf.union(x, y); if (uf.isConnected(0, rows * cols - 1)) { ans = d; break; } }
return ans; }
class UnionFind { int[] parent; int[] size; int count;
public UnionFind(int n) { count = n; parent = new int[n]; size = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; } }
public void union(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX == rootY) { return; } if (size[rootX] < size[rootY]) { parent[rootX] = rootY; size[rootY] += size[rootX]; } else { parent[rootY] = rootX; size[rootX] += size[rootY]; }
count--; }
public int find(int x) { while (x != parent[x]) { parent[x] = parent[parent[x]]; x = parent[x]; }
return x; }
public boolean isConnected(int x, int y) { int rootX = find(x); int rootY = find(y); return rootX == rootY; } }
|
Analysis
- Time Complexity: \(O(mnlog(mn))\).
- Space Complexity: \(O(mn)\).
All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗