Medium

Path With Maximum Minimum Value

LAB

Return the maximum possible minimum cell value along a 4-directional path from top-left to bottom-right.

EXAMPLES

Example 1

Input
{
  "grid": [
    [
      5,
      4,
      5
    ],
    [
      1,
      2,
      6
    ],
    [
      7,
      4,
      6
    ]
  ]
}

Output
4

FUNCTION SHAPE

grid: intMatrix→int

SOLUTION NOTE

If you look at the first greedy solution, it actually isn't technically dijkstra's because there is no relaxation step. (d[curr] > dist + w: d[curr] = dist + w) But it is inspired by dijkstra's, and we can add it in if we want, and the proof of correctness is similar. The reason it works is subtle. It's because we are keeping the min value on the heap. So imagine the cloud. The reason it can't work for max paths, is because there could be a really low cost edge out of the cloud, and then a huge cost edge back into the cloud. But in this case, if we go out of the cloud using a low edge, and then back in using a large edge, the min cost of that path is still at most the path we just popped from the max heap.

I also included a dp + binary search approach that is straightforward, by fixing the min path value.

Reveal reference solution +

pythonREFERENCE

# Dijkstra-inspired greedy
def maximumMinimumPath(self, grid: List[List[int]]) -> int:
    m,n = len(grid), len(grid[0])

    heap = [(-grid[0][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:
        min_val, i, j = heappop(heap)
        min_val = - min_val

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

        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, (- min(min_val, grid[ii][jj]), ii, jj))
    return -1

# Binary search + DFS approach
def maximumMinimumPath(self, grid: List[List[int]]) -> int:
    m,n = len(grid), len(grid[0])

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

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

    @cache
    def dp(i,j, lim):
        if not isInBounds(i,j): return False
        if grid[i][j] < lim: return False
        if (i,j) == (m-1, n-1):
            return True

        if (i,j) in visited: return False
        visited.add((i,j))
        return any(dp(i+x,j+y, lim) for x,y in dirs)

    l,r = min(v for row in grid for v in row), max(v for row in grid for v in row)

    while l < r:
        MID = ceil(l + (r-l)/2)

        visited = set()
        if dp(0, 0, MID):
            l = MID
        else:
            r = MID - 1

    return l

TimeO(m*n*log(m*n))

SpaceO(m*n)

Open on LeetCode ↗