< Back 1631. Path With Minimum Effort For our initial exercise, we're asked to use binary search to solve this problem. This involves executing depth-first search each time we select a maximum distance we'll cover to travel between two points. During our search, we eventually pick a distance that won't allow us to complete the path between point (0, 0) and (m - 1, n - 1) - this will be the minimum effort and our answer. Unfortunately, binary search and the depth-first search for each step had sub-optimal performance. Instead, a way cooler solution involves using UnionFind and disjoint sets. Before we begin to process the graph represented by this matrix, we create a list of edges between nodes on the way from (0, 0) to (m - 1, n - 1), tracking the absolute difference between the nodes of each edge. We then sort our list of edges by difference in increasing order. We process our list of sorted edges, executing UnionFind.union_set() for each node. If we discover that we can reach (m - 1, n - 1) from (0, 0) after UnionFind.union_set()'ing a pair of nodes, we return the difference of the heights between these two nodes - this is the minimum effort required to complete a path between (0, 0) and (m - 1, n - 1). What we've basically accomplished is adding edges with the lowest difference between heights and tracking reachability from (0, 0) to (m - 1, n - 1) for each selection. As soon as we know the end is reachable, we have the difference in heights of the edge just added - and we know this will be the final edge required to make the path with the least amount of effort. The solution is as follows: class UnionFind: def __init__(self, m: int, n: int) -> None: self.rank, self.parent = [0 for _ in range(m * n)], [i for i in range(m * n)] def find(self, x: int) -> int: if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union_set(self, x: int, y: int) -> None: xset, yset = self.find(x), self.find(y) if xset != yset: if self.rank[xset] < self.rank[yset]: xset, yset = yset, xset self.parent[yset] = xset self.rank[xset] += 1 class Solution: def minimumEffortPath(self, heights: List[List[int]]) -> int: m, n = len(heights), len(heights[0]) if m == 1 and n == 1: return 0 edges = [] for i in range(m): for j in range(n): if i > 0: here, there = heights[i][j], heights[i - 1][j] diff = abs(here - there) edges.append((diff, i * n + j, (i - 1) * n + j)) if j > 0: here, there = heights[i][j], heights[i][j - 1] diff = abs(here - there) edges.append((diff, i * n + j, i * n + (j - 1))) edges.sort() uf = UnionFind(m, n) for diff, u, v in edges: uf.union_set(u, v) if uf.find(0) == uf.find(m * n - 1): return diff return -1 _ Time Complexity: O(m * nlog(m * n)) - A UnionFind.find() operation costs log() time, and in the worst case we execute UnionFind.find() m * n times. We have to process m * n edges. _ Space Complexity: O(m * n) - Our edges, rank, and parent lists use m * n space.