< 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.