Path With Maximum Minimum Value

Intuition

Solution

class Solution:
    def maximumMinimumPath(self, A: List[List[int]]) -> int:
        row = len(A)
        col = len(A[0])

        visited = [[False] * col for _ in range(row)]
        minimum = min(A[0][0], A[row - 1][col - 1])
        heap = []
        heapq.heappush(heap, [-A[0][0], 0, 0])
        visited[0][0] = True

        while heap:
            if visited[row - 1][col - 1]:
                return minimum
            v, x, y = heapq.heappop(heap)
            v = -v
            minimum = min(v, minimum)

            for i, j in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
                if 0 <= i < row and 0 <= j < col:
                    if not visited[i][j]:
                        heapq.heappush(heap, [-A[i][j], i, j])
                        visited[i][j] = True