NeetCode #548LC-1102MediumHeap / Priority Queue
← Back to All Problems#548 · #1102 · Path With Maximum Minimum Value(得分最高的路径)
📌 Problem Statement & Constraints
Given an
m x n integer matrix grid, return the maximum possible score of a path from the top-left to the bottom-right corner, where the score is the minimum value along the path. You may move in the four cardinal directions. Constraints: 1 <= m, n <= 100, 1 <= grid[i][j] <= 10^9.💡 Core Algorithmic Approaches
- This is a maximise-the-minimum path problem: use a max-heap keyed by the bottleneck value seen so far.
- Start from
(0, 0)with its value as the bottleneck. - Pop the cell with the largest bottleneck, and push neighbours with
min(current_bottleneck, neighbour_value). - The first time the destination is popped, its bottleneck is the answer -- this is the Dijkstra variant for bottleneck objectives.
💻 Benchmark Python3 Implementation
class Solution:
def maximumMinimumPath(self, grid: List[List[int]]) -> int:
import heapq
m, n = len(grid), len(grid[0])
h = [(-grid[0][0], 0, 0)] # (-bottleneck, r, c)
seen = {(0, 0)}
while h:
neg, r, c = heapq.heappop(h)
cur = -neg # the bottleneck along the best path here
if r == m - 1 and c == n - 1:
return cur
for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and (nr, nc) not in seen:
seen.add((nr, nc))
heapq.heappush(h, (-min(cur, grid[nr][nc]), nr, nc))
return grid[0][0]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(m * n log(m * n)): each cell is pushed once.
💾 Space Complexity
O(m * n) for the heap and the visited set.
⚠️ Interview Pitfalls & Follow-ups
- Using a min-heap: the objective is to maximise the minimum, so the largest bottleneck must be expanded first.
- Marking a cell visited when pushing instead of when popping: with the bottleneck objective, the first pop of a cell is optimal, so marking on push is safe and avoids duplicate pushes.
- Taking
maxinstead ofminalong the path: the path's score is its minimum value. - Only allowing right/down moves: all four directions are permitted.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.