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