NeetCode #602LC-1219MediumGraphs
← Back to All Problems#602 · #1219 · Path with Maximum Gold(黄金矿工)
📌 Problem Statement & Constraints
In a gold mine grid, each cell holds a non-negative amount of gold;
0 means an obstacle. Starting anywhere, you may move in the four cardinal directions but cannot revisit a cell, and cannot enter a 0. Return the maximum gold you can collect. Constraints: 1 <= m, n <= 15, 0 <= grid[i][j] <= 100.💡 Core Algorithmic Approaches
- This is a DFS with backtracking: the path must be simple, so cells are marked and unmarked.
- From every non-zero cell, explore all four directions, accumulating the gold.
- The maximum is tracked at every step (not just at dead ends), since stopping anywhere is allowed.
- The grid is at most 15x15, so the exhaustive search is feasible.
💻 Benchmark Python3 Implementation
class Solution:
def getMaximumGold(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
self.best = 0
def dfs(r: int, c: int, total: int) -> None:
if not (0 <= r < m and 0 <= c < n) or grid[r][c] == 0:
return
gold = grid[r][c]
grid[r][c] = 0 # mark as used (cannot revisit)
total += gold
self.best = max(self.best, total) # stopping here is allowed
for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
dfs(r + dr, c + dc, total)
grid[r][c] = gold # backtrack
for i in range(m):
for j in range(n):
if grid[i][j]:
dfs(i, j, 0)
return self.best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(m * n * 4^(m*n)) worst case, heavily pruned by the obstacle cells.
💾 Space Complexity
O(m * n) for the recursion depth.
⚠️ Interview Pitfalls & Follow-ups
- Only updating the best at dead ends: the path may stop early, so every node is a candidate.
- Forgetting to restore the cell on backtrack: other starting points would see a modified grid.
- Allowing revisits: the problem forbids them.
- Treating
0as collectible: it is an obstacle.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.