Path with Maximum Gold — Solution

Problem

Given a grid of non-negative integers, collect as much gold as possible by starting from any non-zero cell and moving up, down, left, or right — but you cannot visit the same cell twice and cannot step on any cell containing 0.

• Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
• Output: 24
• Explanation: The path 9 → 8 → 7 collects the most gold, starting at the bottom center and moving up then right.

Another valid but suboptimal path is 5 → 8 → 9 = 22, showing that starting cell and direction both matter.

Intuition

The path can branch in any direction and must be able to double back, so you cannot know the best route ahead of time — you have to try them all. The key insight is that you can mark a cell as "visited" by temporarily zeroing it out, recurse into all four neighbors to find the best continuation, then restore the original value so other starting points (or other branches) can use that cell freely.

Solution — Backtracking DFS

Try every non-zero cell as a starting point. For each, run a DFS that explores all simple paths through non-zero neighbors, using in-place zeroing to track the current path and restoring values on the way back.

1. Iterate over every cell; skip cells with 0 gold.
2. For each non-zero cell, call dfs(row, col).
3. In dfs: record the cell's gold, zero it out to mark as visited, then recursively call dfs on all four neighbors.
4. Take the maximum return value across all four directions and add the current cell's gold.
5. Restore the cell's value before returning so other paths can visit it.
6. Track the global maximum across all starting cells.

1def getMaximumGold(grid: list[list[int]]) -> int:
2    rows, cols = len(grid), len(grid[0])
3
4    def dfs(row: int, col: int) -> int:
5        if row < 0 or row >= rows or col < 0 or col >= cols or grid[row][col] == 0:
6            return 0
7
8        current_gold = grid[row][col]
9        grid[row][col] = 0  # zero out so this cell is skipped by nested calls
10
11        best_neighbor = max(
12            dfs(row + 1, col),
13            dfs(row - 1, col),
14            dfs(row, col + 1),
15            dfs(row, col - 1)
16        )
17
18        grid[row][col] = current_gold  # restore so other starting points can use this cell
19        return current_gold + best_neighbor
20
21    max_gold = 0
22    for r in range(rows):
23        for c in range(cols):
24            if grid[r][c] != 0:  # only start paths from cells that have gold
25                max_gold = max(max_gold, dfs(r, c))
26
27    return max_gold

Time: O(m × n × 3^k) where k ≤ 25 is the number of gold cells — each DFS call branches into at most 3 new directions (excluding where it came from), and explores paths up to length k.

Space: O(k) for the recursion call stack, bounded by path length, which is at most the number of gold cells (≤ 25 per problem constraints).

Complexity Summary

Common Mistakes

• Forgetting to restore the cell value after recursion — without grid[row][col] = currentGold on the way back, the cell stays zeroed out permanently, and any other starting path that tries to visit it will find 0 and skip it entirely.
• Starting DFS from zero cells — cells with 0 gold are walls; launching from them always returns 0 and wastes time. Gate the outer loop with if grid[r][c] != 0.
• Not zeroing the current cell before recursing — if you skip this step, a recursive call can return to the same cell, producing an infinite loop or inflated gold totals.
• Assuming DFS without backtracking is enough — a plain DFS that marks cells as permanently visited will miss paths that branch differently from the same starting cell. The restore step is what makes all paths explorable.
• Checking bounds after accessing the grid — always validate row and col before reading grid[row][col], or you'll get an index-out-of-bounds error on edge cells.

Related Problems

• word-search — same in-place mark/restore backtracking pattern on a character grid
• path-sum-ii — backtracking to enumerate all root-to-leaf paths in a tree that sum to a target
• all-paths-from-source-to-target — DFS over all simple paths in a directed acyclic graph
• max-area-of-island — connected-cell flood fill using the same zero-out-to-mark visited trick
• minesweeper — DFS/BFS on a grid that reveals cells based on neighbors, a close structural cousin