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!")