< Back 778. Swim in Rising Water I love graph questions. This is in the binary search section because we could solve this question with binary search, however, UnionFind is way cooler. How would we solve it with binary search you may ask? We're given a matrix of heights, and we're asked to find the first moment in time, t, where we can reach (n - 1, n - 1) from (0, 0). We can only touch a grid location with height, grid[i][j], at time t. Essentially, we're asked to find the minimum maximum across the grid that's going to connect (0, 0) and (n - 1, n - 1). Yeah, so we find the maximum and minimum height across the matrix to create our upper and lower bounds for the binary search. During each iteration of the search, we conduct a search, BFS or DFS, to see if we can reach (n - 1, n - 1). If we can't we need to search towards the right with longer times, and vice versa if we can reach (n - 1, n - 1) - we can probably do it in less time. For UnionFind, we do somemthing different. Instead of searching a bunch of times, we're going to grab all the edges from the graph. Each edge describes the connection between the adjacent nodes, and tracks the maximum height of the pair of nodes. We sort these edges in ascending order - now the edge list has edges in an order where the minimum heights are first and the maximum heights are last. For each edge in this sorted edge list, we connect the two nodes using UnionFind. During each iteration, we check to see if (0, 0) and (n - 1, n - 1) are connected. If they are, we return the height in this edge - this will be the minimum height required to connect (0, 0) and (n - 1, n - 1). Classic connectivity problem, UnionFind is always fun to use for these. 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 swimInWater(self, grid: List[List[int]]) -> int: n = len(grid) if n == 1: return grid[0][0] edges = [] for i in range(n): for j in range(n): if i > 0: edges.append( (max(grid[i][j], grid[i - 1][j]), i * n + j, (i - 1) * n + j) ) if j > 0: edges.append( (max(grid[i][j], grid[i][j - 1]), i * n + j, i * n + (j - 1)) ) edges.sort() uf = UnionFind(n, n) for height, u, v in edges: uf.union_set(u, v) if uf.find(0) == uf.find(n * n - 1): return height return -1 _ Time Complexity: O(n^2 log(n^2)) - We process all edges in the matrix, and we execute UnionFind.find() at most n^2 times. _ Space Complexity: O(n^2) - We store all edges in the matrix.