# 1102. Path With Maximum Minimum Value

Path With Maximum Minimum Value - LeetCode

Given an m x n integer matrix grid, return __the maximum score of a path starting at (0, 0) and ending at __(m - 1, n - 1) moving in the 4 cardinal directions. The score of a path is the minimum value in that path.

``````For example, the score of the path 8 → 4 → 5 → 9 is 4.
``````

Example 1: Input: grid = [[5,4,5],[1,2,6],[7,4,6]] Output: 4 Explanation: The path with the maximum score is highlighted in yellow. Example 2: Input: grid = [[2,2,1,2,2,2],[1,2,2,2,1,2]] Output: 2 Example 3: Input: grid = [[3,4,6,3,4],[0,2,1,1,7],[8,8,3,2,7],[3,2,4,9,8],[4,1,2,0,0],[4,6,5,4,3]] Output: 3

Constraints:

``````m == grid.length
n == grid[i].length
1 <= m, n <= 100
0 <= grid[i][j] <= 109
``````

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

directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]

def dfs(i, j, mini, visited):
if i == m - 1 and j == n - 1:
return True
for dx, dy in directions:
nx, ny = i + dx, j + dy
if 0 <= nx < m and 0 <= ny < n and (nx, ny) not in visited:
if grid[nx][ny] >= mini:
if dfs(nx, ny, mini, visited): return True
return False

res = 0
start, end = 0, min(grid, grid[-1][-1]) + 1 # left open, right closed so plus one
while start < end:
mid = (start + end) // 2
visited = set()