Problem

Given an m x n integer matrix grid, return _the maximumscore 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.

Examples

Example 1:

$$ \Huge \begin{array}{|c|c|c|c|} \hline \colorbox{YellowOrange} 5 & \colorbox{YellowOrange} 4 & \colorbox{YellowOrange} 5 \\ \hline 1 & 2 & \colorbox{YellowOrange} 6 \\ \hline 7 & 4 & \colorbox{YellowOrange} 6 \\ \hline \end{array} $$

1
2
3

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:

$$ \Huge \begin{array}{|c|c|c|c|c|c|} \hline \colorbox{YellowOrange}2 & \colorbox{YellowOrange}2 & 1 & \colorbox{YellowOrange}2 & \colorbox{YellowOrange}2 & \colorbox{YellowOrange}2 \\ \hline 1 & \colorbox{YellowOrange}2 & \colorbox{YellowOrange}2 & \colorbox{YellowOrange}2 & 1 & \colorbox{YellowOrange}2 \\ \hline \end{array} $$

1
2
3

Input: grid = [[2,2,1,2,2,2],[1,2,2,2,1,2]]
Output: 2
Explanation: one valid maximum-minimum path (minimum value = 2) is highlighted above — for example, the route (0,0)→(0,1)→(1,1)→(1,2)→(1,3)→(0,3)→(0,4)→(0,5)→(1,5) (0-based indices: (row,col)).

Example 3:

$$ \Huge \begin{array}{|c|c|c|c|c|} \hline \colorbox{YellowOrange}3 & \colorbox{YellowOrange}4 & \colorbox{YellowOrange}6 & \colorbox{YellowOrange}3 & \colorbox{YellowOrange}4 \\ \hline 0 & 2 & 1 & 1 & \colorbox{YellowOrange}7 \\ \hline \colorbox{YellowOrange}8 & \colorbox{YellowOrange}8 & \colorbox{YellowOrange}3 & 2 & \colorbox{YellowOrange}7 \\ \hline \colorbox{YellowOrange}3 & 2 & \colorbox{YellowOrange}4 & \colorbox{YellowOrange}9 & \colorbox{YellowOrange}8 \\ \hline \colorbox{YellowOrange}4 & 1 & 2 & 0 & 0 \\ \hline \colorbox{YellowOrange}4 & \colorbox{YellowOrange}6 & \colorbox{YellowOrange}5 & \colorbox{YellowOrange}4 & \colorbox{YellowOrange}3 \\ \hline \end{array} $$

1
2
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
Explanation: the highlighted cells show one valid path whose minimum value is 3 (for example: (0,0)→(0,1)→(0,2)→(0,3)→(0,4)→(1,4)→(2,4)→(3,4)→(3,3)→(3,2)→(2,2)→(2,1)→(2,0)→(3,0)→(4,0)→(5,0)→(5,1)→(5,2)→(5,3)→(5,4)).

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 100
  • 0 <= grid[i][j] <= 10^9

Solution

Method 1 - Max-Heap Greedy BFS (Priority Queue)

Intuition

We want the path from (0,0) to (m-1,n-1) whose minimum value along the path is maximized. This is a classic “maximum minimum path” problem, which can be solved using a max-heap (priority queue) with BFS/DFS, or binary search + BFS/DFS/Union-Find.

Approach

Use a max-heap to always expand the path with the highest minimum value so far. For each cell, keep track of the best minimum value to reach it. Stop when we reach the bottom-right cell.

Code

 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
32
33

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

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 = java.util.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
18
19
20

import heapq
from typing import List

class Solution:
    def maximumMinimumPath(self, 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 maximumMinimumPath(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], 0usize, 0usize));
    let dirs = [(0isize,1isize),(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 = x as isize + dx; let ny = y as isize + dy;
            if nx >= 0 && nx < m as isize && ny >= 0 && ny < n as isize && !vis[nx as usize][ny as usize] {
                pq.push((val.min(grid[nx as usize][ny as usize]), nx as usize, ny as usize));
            }
        }
    }
    -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;
}

Complexity

  • ⏰ Time complexity: O(mn log(mn))
  • 🧺 Space complexity: O(mn)