Medium

Path With Minimum Effort

072

Given heights, return the minimum possible maximum absolute difference along a path from top-left to bottom-right.

EXAMPLES

Example 1

Input
{
  "heights": [
    [
      1,
      2,
      2
    ],
    [
      3,
      8,
      2
    ],
    [
      5,
      3,
      5
    ]
  ]
}

Output
2

FUNCTION SHAPE

heights: intMatrix→int

SOLUTION NOTE

Really similar problem to before. Except we want the min max abs adjacent difference path. This clearly will work with dijkstras because we are taking the min path.

Reveal reference solution +

pythonREFERENCE

# Binary search approach
def minimumEffortPath(self, heights: List[List[int]]) -> int:
    m,n = len(heights),len(heights[0])
    l,r = 0, max(max(h) for h in heights) - min(min(h) for h in heights)
    dirs = [(0,1),(1,0),(-1,0),(0,-1)]

    def isInBounds(i,j):
        return 0 <= i < m and 0 <= j < n

    def dfs(i,j,k): # do a dfs/bfs. only move along edges if abs diff is <= k
        if (i,j) == (m-1,n-1): return True
        if (i,j) in visited: return False
        visited.add((i,j))
        return any(dfs(i+x,j+y,k) for x,y in dirs if isInBounds(i+x,j+y) and abs(heights[i][j] - heights[i+x][j+y]) <= k)

    while l < r:
        mid = l+(r-l)//2
        visited = set()
        if dfs(0,0,mid):
            r = mid
        else:
            l = mid + 1
    return l

# Dijkstra's approach
def minimumEffortPath(self, grid: List[List[int]]) -> int:
    m,n = len(grid), len(grid[0])

    heap = [(0, 0, 0)]

    dirs = [(0,1), (0,-1), (1,0), (-1,0)]

    visited = set()

    def isInBounds(i,j):
        return 0 <= i < m and 0 <= j < n

    while heap:
        effort, i, j = heappop(heap)

        if (i,j) == (m-1,n-1):
            return effort

        if (i,j) in visited: continue
        visited.add((i,j))

        for x,y in dirs:
            ii = i + x
            jj = j + y

            if isInBounds(ii,jj):
                heappush(heap, (max(effort, abs(grid[ii][jj] - grid[i][j])), ii, jj))

    return -1

TimeO(m*n*log(max_height))

SpaceO(m*n)

Open on LeetCode ↗