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:

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:

1
2

Input: grid = [[2,2,1,2,2,2],[1,2,2,2,1,2]]
Output: 2

Example 3:

1
2

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] <= 10^9

Solution

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

C++
 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;
    }
};
Go
 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 } }
Java
 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;
    }
}
Kotlin
 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
    }
}
Python
 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
Rust
 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
}
TypeScript
 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)