publicintminimumEffortPath(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(newint[]{index - cols, index, Math.abs(heights[i][j] - heights[i - 1][j])}); }
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; }
classUnionFind{ int[] parent; int[] size; int count;
publicUnionFind(int n){ count = n; parent = newint[n]; size = newint[n]; for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; } }
publicvoidunion(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--; }
publicintfind(int x){ while (x != parent[x]) { parent[x] = parent[parent[x]]; x = parent[x]; }
return x; }
publicbooleanisConnected(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:-)