https://leetcode.com/problems/path-with-minimum-effort

Let us use dfs function with parameter LIMIT here: it is the maximum effort hiker can deal with. Then the idea is to use binary search to find the smallest LIMIT for which hiker can reach the ending point.

So, what we have here is just dfs(LIMIT, x, y), where LIMIT is maximum effort we can deal and x, y are current coordinates. To perform dfs, we need to visit all neighbors, make sure that we:

  1. Do not go outside our grid
  2. Cell is not visited yet
  3. Effort to go from old cell to new one is less or equal than LIMIT.

Now we can perform binary search part:

  1. We can be sure, that if LIMIT = -1, we never reach end, and if LIMIT is maximum over all heights, than we will reach end.
  2. Choose middle point, clean visited set of cells, perform dfs and choose left or right part to search.

Complexity: Each dfs will take O(mn) time and we will have O(log H) steps in binary search, where H is biggest number in our grid we have, so final time complexity is O(mn log H). Space compexity is O(mn) to keep visited set.

class Solution:
    def minimumEffortPath(self, heights):
        m, n = len(heights), len(heights[0])
        neibs = [[1, 0], [0, 1], [-1, 0], [0, -1]]
        
        def dfs(LIMIT, x, y):
            visited.add((x, y)) 
            for dx, dy in neibs:
                if 0<=dx+x<m and 0<=dy+y<n and (dx+x, dy+y) not in visited:
                    if abs(heights[x][y] - heights[dx+x][dy+y]) <= LIMIT:
                        dfs(LIMIT, dx+x, dy+y)
        
        beg, end = -1, max(max(heights, key=max))
        while beg + 1 < end:
            mid = (beg + end)//2
            visited = set()
            dfs(mid, 0, 0)
            if (m - 1, n - 1) in visited:
                end = mid
            else:
                beg = mid
                
        return end

Further thoughts:

  1. There is Union Find solution: we need to create all O(mn) edges in our graph, sort them in increasing order and then add them one by one, each time asking question: can we go from start to end, that is if start and end are in the same disjoint set. Complexity will be O(mn log(mn)), which in practive works several times faster.
  2. There is also Heap solution, which most people in discussion refer as Dijkstra algorithm, the idea is the following: for each cell keep the minimum effort we need to have to reach this node. Each moment of time we will extract cell with minimum effort, look at its neighbors and put them to heap. Complexity also will be O(mn log(mn))

See similar problem 778 Swim in Rising Water

If you like the solution, you can upvote it on leetcode discussion section: Problem 1631