Problem Breakdown
We are given an m x n 2D integer array representing a gold mine where each cell contains either gold or is empty (0). Our goal is to find the maximum amount of gold we can collect. We start at any non-zero cell and move up, down, left, or right. Crucially:
- No revisiting: Once you step on a cell in your current path, it cannot be visited again during that specific traversal (prevents cycles).
- Empty cells are walls: We can never enter a
0value cell. - Flexible Start/Stop: The optimal path doesn’t have to start at
(0,0)or end there; we scan all potential starting points with gold > 0.
Inputs: A list of lists (grid) containing integers between 0 and 100. Dimensions up to 15 x 15.
Output: An integer representing the maximum sum collected in a single valid path.
Tricky Constraints: The grid is small, but dense backtracking can be slow (). However, there are at most 25 cells with gold. This sparsity is the key to performance; we only traverse nodes that contain value > 0.
Intuition
This problem asks for a path in an undirected graph where edges exist between adjacent non-zero cells and node weights sum up along the path without cycles (simple paths).
- Brute Force: Try every cell as a start point, then try all permutations of neighbors to find the longest weighted simple path. This is essentially finding the maximum weight Hamiltonian Path on subgraphs induced by gold nodes.
- Why Brute Force Fails: A naive DFS without pruning would explore states in a dense grid, which TLEs (Time Limit Exceeded). However, since we can’t step on
0and there are at most 25 gold nodes, the effective search space is bounded by permutations of these sparse nodes. - Optimal Approach: Use Depth-First Search (DFS) with Backtracking. For every cell containing gold:
- Treat it as a starting point for a path.
- Mark current cell as visited to prevent cycles in the current recursion stack.
- Recursively explore valid neighbors (up, down, left, right).
- Backtrack: Before returning from the recursive call, restore the grid value so other paths can utilize this gold later. This avoids allocating a separate
visitedmatrix for every start node.
Approach
- Initialize a global or closure-scoped variable
max_gold = 0. - Iterate through every cell
(i, j)in the grid:- If
grid[i][j] > 0, initiate a DFS from this position to find paths starting here.
- If
- Define the recursive helper function
dfs(r, c):- Base Case: Return current accumulated gold sum (though we usually update an outer max).
- Mark Visited: Temporarily set
grid[r][c] = 0to mark as visited for this specific path. This modifies the input in-place which is efficient but requires restoration later. - Explore Neighbors: For each direction
(dr, dc):- Check bounds (
r + dr,c + dc). - Ensure neighbor has gold (
grid[r+dr][c+dc] > 0). - Recurse:
current_gold = dfs(new_r, new_c)(or simply accumulate in the loop).
- Check bounds (
- Backtrack: Restore
grid[r][c]to its original value before returning. This allows other paths starting from different points or branches to use this cell again.
- Update
max_goldwith the result of each DFS traversal. - Return
max_gold.
Complexity Analysis
- Time Complexity: where is the number of cells containing gold (at most 25). In a grid, from any cell you have at most 4 neighbors; since we came from one direction and can’t go back immediately in DFS without revisiting logic, effective branching factor reduces. Given the constraint that there are only non-zero nodes, this exponential complexity is well within limits for typical time constraints (usually ~10^8 operations per second).
- Space Complexity: where is the number of gold cells in the recursion stack. In the worst case path length equals the total count of gold cells. We do not use extra space for a
visitedset if we modify the grid, but technically modifying input might be considered side-effect dependent; however, standard backtracking solutions often accept this trade-off or pass the visited state via arguments to save stack overhead compared to allocating new sets at every step.
Solution
class Solution:
def getMaximumGold(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
# Helper function for DFS backtracking
def dfs(r, c):
current_gold = 0
# Mark cell as visited by setting gold to 0 temporarily
temp_val = grid[r][c]
grid[r][c] = 0
max_path_from_here = 0
# Explore all valid directions: up, down, left, right
for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] > 0:
max_path_from_here += dfs(nr, nc)
# Backtrack: Restore the gold value for other paths to use this cell later
grid[r][c] = temp_val
return current_gold + max_path_from_here
global_max = 0
# Iterate over every cell as a potential starting point
for r in range(m):
for c in range(n):
if grid[r][c] > 0:
# Start DFS from this gold-containing cell
current_total_gold = dfs(r, c) + grid[r][c]
# Note: The logic above accumulates inside the loop.
# To simplify accumulation without double counting in recursion structure:
pass
# Refining the helper to return sum correctly including start node
def backtrack(r, c):
current_gold = 0
# Temporarily mark as visited (set to 0)
grid[r][c] = 0
max_val = 0
for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] > 0:
max_val += backtrack(nr, nc)
# Restore original value for backtracking purposes
grid[r][c] = temp_gold
return current_gold + max_val
global_max = 0
def dfs(r, c):
gold_collected = 0
# Mark visited by setting to 0 temporarily
saved_val = grid[r][c]
grid[r][c] = 0
for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] > 0:
gold_collected += dfs(nr, nc)
# Restore the cell value before returning (backtracking step)
grid[r][c] = saved_val
return gold_collected + saved_val
for r in range(m):
for c in range(n):
if grid[r][c] > 0:
global_max = max(global_max, dfs(r, c))
return global_max