Leetcode 1099 Solution

This article provides solution to leetcode question 1099 (path-with-maximum-minimum-value)
Categories:
Tags:
Access this page by simply typing in "lcs 1099" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/path-with-maximum-minimum-value

Solution

class Solution:
    def maximumMinimumPath(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])



        q = []
        visited = set()



        heapq.heappush(q, (-grid[0][0], 0, 0))



        while q:
            score, i, j = heapq.heappop(q)



            if (i, j) in visited:
                continue



            visited.add((i, j))



            if i == m - 1 and j == n - 1:
                return -score



            for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                ni = i + di
                nj = j + dj



                if not (0 <= ni < m and 0 <= nj < n):
                    continue



                if (ni, nj) in visited:
                    continue



                heapq.heappush(q, (max(score, -grid[ni][nj]), ni, nj))



        raise Exception("Fatal!")