LeetCode 1102 - Path With Maximum Minimum Value

The problem asks us to find the maximum possible score of a path from the top-left corner (0, 0) to the bottom-right corner (m-1, n-1) of a 2D grid. Each cell in the grid contains an integer value, and the score of a path is defined as the minimum value along that path.

leetcodemediumarraybinary-searchdepth-first-searchbreadth-first-searchunion-findheap-(priority-queue)matrix

LeetCode Problem 1102

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Depth-First Search, Breadth-First Search, Union-Find, Heap (Priority Queue), Matrix

Solution

Problem Understanding

The problem asks us to find the maximum possible score of a path from the top-left corner (0, 0) to the bottom-right corner (m-1, n-1) of a 2D grid. Each cell in the grid contains an integer value, and the score of a path is defined as the minimum value along that path. In other words, if a path goes through numbers [8, 4, 5, 9], the score of that path is 4 because it is the smallest number on that path.

The input is an m x n integer matrix grid, and we can move in the four cardinal directions (up, down, left, right). The goal is to find the path that maximizes the minimum value along the path.

Constraints indicate that m and n are up to 100, and each grid value can be as large as 1 billion. Therefore, naive solutions that explore every path are computationally infeasible. Edge cases to consider include grids with the smallest possible values (0) or where the largest minimum value is on a path that does not follow the obvious high-value cells.

Important guarantees include that the grid always has at least one cell, and we can always reach the destination because the grid is finite and connected.

Approaches

A brute-force approach would be to explore all possible paths from (0, 0) to (m-1, n-1) and compute the minimum value along each path. Then, we would select the maximum of these minimums. This is correct in theory but computationally infeasible because the number of paths grows exponentially with the grid size, specifically O(4^(m*n)).

The key insight for an optimal solution is that we do not need to compute every path explicitly. Instead, we can use a priority-based search such as a max-heap BFS or a Union-Find approach. The idea is to prioritize visiting cells with higher values first. In a max-heap BFS, we always expand the current cell with the largest value available, ensuring that the minimum value along the path is as high as possible. This approach guarantees that the first time we reach the bottom-right cell, we have found the maximum minimum score.

Approach Time Complexity Space Complexity Notes
Brute Force O(4^(m*n)) O(m*n) Explore all paths and compute minimum for each
Optimal (Max-Heap BFS) O(m_n_log(m*n)) O(m*n) Use priority queue to expand highest-value paths first

Algorithm Walkthrough

  1. Initialize a max-heap (priority queue) with the starting cell (0, 0) and its value. The heap stores tuples (value, row, col), and we negate value because most heap implementations are min-heaps.
  2. Create a visited matrix to track which cells have already been processed.
  3. Initialize a variable score to track the minimum value along the path as we traverse.
  4. While the heap is not empty, pop the cell with the maximum value.
  5. Update score as the minimum of the current score and the cell's value.
  6. If we reach the bottom-right cell (m-1, n-1), return score because this is the maximum minimum path due to the max-heap property.
  7. For each neighboring cell (up, down, left, right), if it is within bounds and not visited, mark it visited and push it onto the heap.
  8. Continue until the destination is reached.

Why it works: By always expanding the largest available cell first, the path that reaches the bottom-right corner first will have the maximum possible minimum value. Lower-valued paths are ignored because they cannot produce a higher minimum.

Python Solution

from typing import List
import heapq

class Solution:
    def maximumMinimumPath(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        max_heap = [(-grid[0][0], 0, 0)]
        visited = [[False]*n for _ in range(m)]
        visited[0][0] = True
        score = grid[0][0]

        directions = [(0,1),(1,0),(-1,0),(0,-1)]

        while max_heap:
            value, x, y = heapq.heappop(max_heap)
            value = -value
            score = min(score, value)
            if x == m-1 and y == n-1:
                return score
            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(max_heap, (-grid[nx][ny], nx, ny))

Implementation walkthrough: We initialize a max-heap with the start cell. The visited matrix prevents cycles. At each step, we pop the highest-value cell from the heap and update score to track the minimum along the path. The first time we reach the destination, score reflects the maximum minimum value because the algorithm always explores the largest available options first.

Go Solution

package main

import (
    "container/heap"
)

type Cell struct {
    value, x, y int
}

type MaxHeap []Cell

func (h MaxHeap) Len() int { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i].value > h[j].value }
func (h MaxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(v interface{}) { *h = append(*h, v.(Cell)) }
func (h *MaxHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func maximumMinimumPath(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    visited := make([][]bool, m)
    for i := range visited {
        visited[i] = make([]bool, n)
    }
    h := &MaxHeap{{grid[0][0], 0, 0}}
    heap.Init(h)
    visited[0][0] = true
    score := grid[0][0]

    dirs := [][]int{{0,1},{1,0},{0,-1},{-1,0}}

    for h.Len() > 0 {
        cell := heap.Pop(h).(Cell)
        score = min(score, cell.value)
        if cell.x == m-1 && cell.y == n-1 {
            return score
        }
        for _, d := range dirs {
            nx, ny := cell.x + d[0], cell.y + d[1]
            if nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny] {
                visited[nx][ny] = true
                heap.Push(h, Cell{grid[nx][ny], nx, ny})
            }
        }
    }
    return score
}

func min(a, b int) int {
    if a < b { return a }
    return b
}

Go-specific notes: Go requires a custom MaxHeap implementation using container/heap. Unlike Python, Go does not have a built-in max-heap, so we invert the comparison. We also explicitly define a Cell struct to store coordinates and values. Slices are used for visited and directions.

Worked Examples

Example 1: grid = [[5,4,5],[1,2,6],[7,4,6]]

Step by step:

Step Heap (value,x,y) Score Action
1 [(5,0,0)] 5 pop start cell
2 [(4,0,1),(1,1,0)] min(5,5)=5 push neighbors
3 [(4,0,1),(1,1,0)] min(5,4)=4 pop (0,1)
4 [...] ... continue expanding until (2,2)
Final Reached (2,2) 4 maximum minimum path found

Example 2 and Example 3 follow similar steps, always expanding the highest-value cells first.

Complexity Analysis

Measure Complexity Explanation
Time O(m_n_log(m*n)) Each cell is pushed/popped from the heap once; heap operations are O(log(m*n))
Space O(m*n) The visited matrix and heap may store up to all cells

The algorithm is efficient because it avoids exploring unnecessary paths with smaller values and guarantees that the first path reaching the destination has the maximum minimum.

Test Cases

# provided examples
assert Solution().maximumMinimumPath([[5,4,5],[1,2,6],[7,4,6]]) == 4  # example 1
assert Solution().maximumMinimumPath([[2,2,1,2,2,2],[1,2,2