Path With Maximum Minimum Value

1
2
3
4

![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/1100-1199/1102.Path%20With%20Maximum%20Minimum%20Value/images/maxgrid1.jpg)
Input: grid = [[5,4,5],[1,2,6],[7,4,6]]
Output: 4
Explanation: The path with the maximum score is highlighted in yellow. 

1
2
3

![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/1100-1199/1102.Path%20With%20Maximum%20Minimum%20Value/images/maxgrid2.jpg)
Input: grid = [[2,2,1,2,2,2],[1,2,2,2,1,2]]
Output: 2

1
2
3

![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/1100-1199/1102.Path%20With%20Maximum%20Minimum%20Value/images/maxgrid3.jpg)
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
    int maximumMinimumPath(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> vis(m, vector<int>(n, 0));
        priority_queue<tuple<int,int,int>> pq;
        pq.emplace(grid[0][0], 0, 0);
        int dirs[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
        while (!pq.empty()) {
            auto [val, x, y] = pq.top(); pq.pop();
            if (x == m-1 && y == n-1) return val;
            if (vis[x][y]) continue;
            vis[x][y] = 1;
            for (auto& d : dirs) {
                int nx = x + d[0], ny = y + d[1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && !vis[nx][ny])
                    pq.emplace(min(val, grid[nx][ny]), nx, ny);
            }
        }
        return -1;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

import "container/heap"
type Item struct{ val, x, y int }
type PQ []Item
func (h PQ) Len() int { return len(h) }
func (h PQ) Less(i, j int) bool { return h[i].val > h[j].val }
func (h PQ) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *PQ) Push(x any) { *h = append(*h, x.(Item)) }
func (h *PQ) Pop() any { old := *h; x := old[len(old)-1]; *h = old[:len(old)-1]; return x }
func maximumMinimumPath(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    vis := make([][]bool, m)
    for i := range vis { vis[i] = make([]bool, n) }
    pq := &PQ{{grid[0][0], 0, 0}}
    heap.Init(pq)
    dirs := [][2]int{{0,1},{1,0},{0,-1},{-1,0}}
    for pq.Len() > 0 {
        item := heap.Pop(pq).(Item)
        val, x, y := item.val, item.x, item.y
        if x == m-1 && y == n-1 { return val }
        if vis[x][y] { continue }
        vis[x][y] = true
        for _, d := range dirs {
            nx, ny := x+d[0], y+d[1]
            if nx >= 0 && nx < m && ny >= 0 && ny < n && !vis[nx][ny] {
                heap.Push(pq, Item{min(val, grid[nx][ny]), nx, ny})
            }
        }
    }
    return -1
}
func min(a, b int) int { if a < b { return a } else { return b } }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import java.util.*;
class Solution {
    public int maximumMinimumPath(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        boolean[][] vis = 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[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int val = cur[0], x = cur[1], y = cur[2];
            if (x == m-1 && y == n-1) return val;
            if (vis[x][y]) continue;
            vis[x][y] = true;
            for (int[] d : dirs) {
                int nx = x + d[0], ny = y + d[1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && !vis[nx][ny])
                    pq.offer(new int[]{Math.min(val, grid[nx][ny]), nx, ny});
            }
        }
        return -1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

import java.util.PriorityQueue
class Solution {
    fun maximumMinimumPath(grid: Array<IntArray>): Int {
        val m = grid.size; val n = grid[0].size
        val vis = Array(m) { BooleanArray(n) }
        val pq = PriorityQueue(compareByDescending<Triple<Int,Int,Int>> { it.first })
        pq.add(Triple(grid[0][0], 0, 0))
        val dirs = arrayOf(0 to 1, 1 to 0, 0 to -1, -1 to 0)
        while (pq.isNotEmpty()) {
            val (val_, x, y) = pq.poll()
            if (x == m-1 && y == n-1) return val_
            if (vis[x][y]) continue
            vis[x][y] = true
            for ((dx, dy) in dirs) {
                val nx = x + dx; val ny = y + dy
                if (nx in 0 until m && ny in 0 until n && !vis[nx][ny])
                    pq.add(Triple(minOf(val_, grid[nx][ny]), nx, ny))
            }
        }
        return -1
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

import heapq
def maximumMinimumPath(grid: list[list[int]]) -> int:
    m, n = len(grid), len(grid[0])
    vis = [[False]*n for _ in range(m)]
    pq = [(-grid[0][0], 0, 0)]
    while pq:
        val, x, y = heapq.heappop(pq)
        val = -val
        if x == m-1 and y == n-1:
            return val
        if vis[x][y]: continue
        vis[x][y] = True
        for dx, dy in ((0,1),(1,0),(0,-1),(-1,0)):
            nx, ny = x+dx, y+dy
            if 0 <= nx < m and 0 <= ny < n and not vis[nx][ny]:
                heapq.heappush(pq, (-min(val, grid[nx][ny]), nx, ny))
    return -1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

use std::collections::BinaryHeap;
fn maximum_minimum_path(grid: Vec<Vec<i32>>) -> i32 {
    let (m, n) = (grid.len(), grid[0].len());
    let mut vis = vec![vec![false; n]; m];
    let mut pq = BinaryHeap::new();
    pq.push((grid[0][0], 0, 0));
    let dirs = [(0,1),(1,0),(0,-1),(-1,0)];
    while let Some((val, x, y)) = pq.pop() {
        if x == m-1 && y == n-1 { return val; }
        if vis[x][y] { continue; }
        vis[x][y] = true;
        for (dx, dy) in dirs.iter() {
            let (nx, ny) = (x+dx, y+dy);
            if nx >= 0 && nx < m as i32 && ny >= 0 && ny < n as i32 && !vis[nx as usize][ny as usize] {
                pq.push((val.min(grid[nx as usize][ny as usize]), nx, ny));
            }
        }
    }
    -1
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

function maximumMinimumPath(grid: number[][]): number {
    const m = grid.length, n = grid[0].length;
    const vis = Array.from({length: m}, () => Array(n).fill(false));
    const pq: [number, number, number][] = [[grid[0][0], 0, 0]];
    pq.sort((a, b) => b[0] - a[0]);
    const dirs = [[0,1],[1,0],[0,-1],[-1,0]];
    while (pq.length) {
        const [val, x, y] = pq.shift()!;
        if (x === m-1 && y === n-1) return val;
        if (vis[x][y]) continue;
        vis[x][y] = true;
        for (const [dx, dy] of dirs) {
            const nx = x+dx, ny = y+dy;
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && !vis[nx][ny])
                pq.push([Math.min(val, grid[nx][ny]), nx, ny]);
        }
        pq.sort((a, b) => b[0] - a[0]);
    }
    return -1;
}