⚡Flashcard Drill➔
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

  1. This is a maximise-the-minimum path problem: use a max-heap keyed by the bottleneck value seen so far.
  2. Start from (0, 0) with its value as the bottleneck.
  3. Pop the cell with the largest bottleneck, and push neighbours with min(current_bottleneck, neighbour_value).
  4. 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 max instead of min along 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.
🎯 Drill This Card Now➔

🧩 Related Heap / Priority Queue Problems