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