Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1102. Path With Maximum Minimum Value - Leetcode Solution

Code Implementation

import heapq

class Solution:
    def maximumMinimumPath(self, grid):
        m, n = len(grid), len(grid[0])
        visited = [[False]*n for _ in range(m)]
        # Max heap: use negative values because heapq is min-heap by default
        heap = [(-grid[0][0], 0, 0)]
        directions = [(0,1), (1,0), (0,-1), (-1,0)]
        visited[0][0] = True

        while heap:
            val, x, y = heapq.heappop(heap)
            val = -val
            if x == m-1 and y == n-1:
                return val
            for dx, dy in directions:
                nx, ny = x+dx, y+dy
                if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny]:
                    visited[nx][ny] = True
                    heapq.heappush(heap, (-min(val, grid[nx][ny]), nx, ny))

#include <vector>
#include <queue>
#include <tuple>

using namespace std;

class Solution {
public:
    int maximumMinimumPath(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        priority_queue<tuple<int,int,int>> pq;
        pq.emplace(grid[0][0], 0, 0);
        visited[0][0] = true;
        vector<pair<int,int>> dirs = {{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;
            for (auto& d : dirs) {
                int nx = x + d.first, ny = y + d.second;
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    pq.emplace(min(val, grid[nx][ny]), nx, ny);
                }
            }
        }
        return -1;
    }
};

import java.util.*;

class Solution {
    public int maximumMinimumPath(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        pq.offer(new int[]{grid[0][0], 0, 0});
        visited[0][0] = true;
        int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int val = curr[0], x = curr[1], y = curr[2];
            if (x == m-1 && y == n-1) return val;
            for (int[] d : dirs) {
                int nx = x + d[0], ny = y + d[1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    pq.offer(new int[]{Math.min(val, grid[nx][ny]), nx, ny});
                }
            }
        }
        return -1;
    }
}

class PriorityQueue {
    constructor() {
        this.data = [];
    }
    push(item) {
        this.data.push(item);
        this.data.sort((a, b) => b[0] - a[0]);
    }
    pop() {
        return this.data.shift();
    }
    isEmpty() {
        return this.data.length === 0;
    }
}

var maximumMinimumPath = function(grid) {
    let m = grid.length, n = grid[0].length;
    let visited = Array.from({length: m}, () => Array(n).fill(false));
    let pq = new PriorityQueue();
    pq.push([grid[0][0], 0, 0]);
    visited[0][0] = true;
    let dirs = [[0,1],[1,0],[0,-1],[-1,0]];
    while (!pq.isEmpty()) {
        let [val, x, y] = pq.pop();
        if (x === m-1 && y === n-1) return val;
        for (let [dx, dy] of dirs) {
            let nx = x + dx, ny = y + dy;
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
                visited[nx][ny] = true;
                pq.push([Math.min(val, grid[nx][ny]), nx, ny]);
            }
        }
    }
    return -1;
};

Problem Description

Given a 2D grid of integers grid, you start at the top-left cell (0, 0) and want to reach the bottom-right cell (m-1, n-1) by moving only up, down, left, or right. Each cell contains a value. The score of a path is the minimum value encountered along that path. Your task is to find a path from the start to the end such that this minimum value is as large as possible (i.e., maximize the minimum value along the path). Each cell can be used at most once in the path.
  • There is always at least one valid path.
  • You cannot reuse any cell in your path.
  • Return the maximum possible minimum value of any path from the top-left to the bottom-right.

Thought Process

At first glance, you might think of finding all possible paths from the top-left to the bottom-right and, for each path, calculating the smallest value along that path. Then, you would take the largest of these minimums. However, this brute-force approach is computationally infeasible for large grids because the number of paths grows exponentially with the grid size. Instead, we need a smarter way. Notice that we want to maximize the minimum value along the path, which is similar to a "best worst-case" scenario. This hints at using a greedy or priority-based search, where at each step we prefer moving into the cell with the highest possible value, trying to keep our minimum as high as possible. This leads us to algorithms like Dijkstra's (but maximizing the minimum value instead of minimizing the sum).

Solution Approach

To solve this problem efficiently, we use a variation of Dijkstra's algorithm, but instead of summing distances, we track the minimum value along the path so far and always prioritize paths with higher minimums.
  1. Initialization:
    • Create a max-heap (priority queue) where each entry stores: (current path's minimum value so far, row, column).
    • Start by pushing the top-left cell with its value as the minimum.
    • Maintain a visited matrix to avoid revisiting cells.
  2. Processing:
    • At each step, pop the cell with the highest minimum value from the heap.
    • If it's the bottom-right cell, return its minimum value (since we process highest-minimum paths first, it's optimal).
    • For each unvisited neighbor (up, down, left, right), compute the new minimum (the smaller of the current minimum and the neighbor's value), and push this into the heap.
    • Mark neighbors as visited upon pushing to avoid cycles.
  3. Termination:
    • When we reach the bottom-right cell, we've found the path whose minimum value is largest possible.
This approach ensures that we always explore the most promising (highest minimum so far) paths first, guaranteeing the optimal solution.

Example Walkthrough

Consider the grid: 

  grid = [
    [5, 4, 5],
    [1, 2, 6],
    [7, 4, 6]
  ]
  1. We start at (0,0) with value 5. The initial minimum is 5.
  2. Possible moves: (0,1) with value 4 and (1,0) with value 1.
    • Path to (0,1): min(5,4)=4
    • Path to (1,0): min(5,1)=1
  3. We always pick the path with the highest minimum, so we proceed with (0,1) first (min=4).
  4. From (0,1), possible moves: (0,2) with value 5, (1,1) with value 2.
    • Path to (0,2): min(4,5)=4
    • Path to (1,1): min(4,2)=2
  5. Again, pick (0,2) (min=4). From here, move to (1,2) with value 6: min(4,6)=4.
  6. From (1,2), move to (2,2) with value 6: min(4,6)=4.
  7. We have reached the bottom-right with a path minimum of 4.
  8. Other paths will have smaller minimums, so 4 is the answer.

Time and Space Complexity

  • Brute-force approach: Exponential time O(2^{m+n}) due to all possible paths, which is not feasible for large grids.
  • Optimized approach (priority queue / Dijkstra variant):
    • Time Complexity: O(mn \log(mn)) because each cell is pushed into the heap at most once, and heap operations take O(\log(mn)).
    • Space Complexity: O(mn) for the visited matrix and the heap.

Summary

The key to solving "Path With Maximum Minimum Value" is recognizing that we want the "best worst-case" path. By using a max-heap and always exploring the path with the highest minimum value so far, we guarantee that the first time we reach the destination, it is through the optimal path. This approach is both efficient and elegant, transforming a potentially exponential problem into a tractable one using a greedy, Dijkstra-like strategy.