Path With Maximum Minimum Value
Problem
Given an m × n grid, find a path from (0,0) to (m-1, n-1) (moving in four directions) that maximizes the minimum value along the path. Return that minimum.
grid = [[5,4,5],[1,2,6],[7,4,6]]4import heapq
def maximum_minimum_path(grid):
m, n = len(grid), len(grid[0])
seen = [[False]*n for _ in range(m)]
# max-heap of (-value, r, c)
heap = [(-grid[0][0], 0, 0)]
while heap:
neg, r, c = heapq.heappop(heap)
v = -neg
if seen[r][c]: continue
seen[r][c] = True
if r == m-1 and c == n-1:
return v
for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
nr, nc = r+dr, c+dc
if 0 <= nr < m and 0 <= nc < n and not seen[nr][nc]:
heapq.heappush(heap, (-min(v, grid[nr][nc]), nr, nc))function maximumMinimumPath(grid) {
const m = grid.length, n = grid[0].length;
const seen = Array.from({length: m}, () => Array(n).fill(false));
// simple "max-heap": pop max each loop
const heap = [[grid[0][0], 0, 0]];
while (heap.length) {
heap.sort((a, b) => b[0] - a[0]);
const [v, r, c] = heap.shift();
if (seen[r][c]) continue;
seen[r][c] = true;
if (r === m-1 && c === n-1) return v;
for (const [dr, dc] of [[1,0],[-1,0],[0,1],[0,-1]]) {
const nr = r+dr, nc = c+dc;
if (nr>=0 && nr<m && nc>=0 && nc<n && !seen[nr][nc])
heap.push([Math.min(v, grid[nr][nc]), nr, nc]);
}
}
}class Solution {
public int maximumMinimumPath(int[][] grid) {
int m = grid.length, n = grid[0].length;
boolean[][] seen = new boolean[m][n];
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
pq.offer(new int[]{grid[0][0], 0, 0});
int[][] D = {{1,0},{-1,0},{0,1},{0,-1}};
while (!pq.isEmpty()) {
int[] t = pq.poll(); int v = t[0], r = t[1], c = t[2];
if (seen[r][c]) continue;
seen[r][c] = true;
if (r == m-1 && c == n-1) return v;
for (int[] d : D) {
int nr = r+d[0], nc = c+d[1];
if (nr>=0 && nr<m && nc>=0 && nc<n && !seen[nr][nc])
pq.offer(new int[]{Math.min(v, grid[nr][nc]), nr, nc});
}
}
return -1;
}
}int maximumMinimumPath(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<bool>> seen(m, vector<bool>(n, false));
priority_queue<tuple<int,int,int>> pq;
pq.emplace(grid[0][0], 0, 0);
int D[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
while (!pq.empty()) {
auto [v, r, c] = pq.top(); pq.pop();
if (seen[r][c]) continue;
seen[r][c] = true;
if (r == m-1 && c == n-1) return v;
for (auto& d : D) {
int nr = r+d[0], nc = c+d[1];
if (nr>=0 && nr<m && nc>=0 && nc<n && !seen[nr][nc])
pq.emplace(min(v, grid[nr][nc]), nr, nc);
}
}
return -1;
}Explanation
We want a path whose weakest cell is as strong as possible. The trick is a Dijkstra-style search with a max-heap: always expand from the cell whose "min-value-so-far" is the largest, so the first time we pop the bottom-right corner we already have the best possible bottleneck.
The heap stores entries keyed by the minimum cell value along the path taken to reach a cell. The Python version pushes (-value, r, c) so the smallest negative (largest value) comes out first. We start at (0,0) with its own value as the running minimum.
Each time we pop a cell, we mark it seen. For each unvisited neighbor we push min(v, grid[nr][nc]) — the path's bottleneck can only stay the same or drop when we add a new cell. Because we always pop the best bottleneck first, reaching the goal gives the maximized minimum.
The if seen[r][c]: continue check skips stale heap entries so each cell is finalized once, at its best value.
Example: grid = [[5,4,5],[1,2,6],[7,4,6]]. The path 5 → 4 → 5 → 6 → 6 has minimum 4, and no path can keep its minimum above 4, so the answer is 4.