Problem statement

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

Solution

This problem is almost identical to problem 0778. Swim in Rising Water, the difference here is that we need to start with big values and instead of small. The following is the solution using heaps.

Complexity

It is O(MN*log MN) for time and O(MN) for space.

Code

class Solution:
    def maximumMinimumPath(self, grid):
        M, N = len(grid), len(grid[0])
        heap, visited, res = [(-grid[0][0], 0, 0)], set([(0, 0)]), -float("inf")
        
        for i in range(N*M):
            val, x, y = heappop(heap)
            res = max(res, val)
            if x == M-1 and y == N-1: return -res
            neib_list = [[0,1],[0,-1],[1,0],[-1,0]]
            
            for dx, dy in neib_list:
                if (x + dx, y + dy) not in visited and 0<=x+dx<M and 0<=y+dy<N:
                    heappush(heap, (-grid[x+dx][y+dy], x+dx, y+dy))
                    visited.add((x+dx, y+dy))