Path with Maximum Gold: Backtracking on a Grid

You are given an m x n grid where each cell contains a non-negative integer representing the amount of gold in that cell. A value of 0 means the cell is empty and you cannot pass through it. Starting from any cell with gold, you can walk to any of the four adjacent cells (up, down, left, right) as long as the next cell has gold and you have not visited it before. Return the maximum amount of gold you can collect along any path.

This is LeetCode 1219: Path with Maximum Gold, and it is one of the cleanest examples of backtracking on a 2D grid. The technique it teaches applies to any problem where you need to explore all possible paths through a grid and track the best result.

Why this problem matters

Grid backtracking shows up constantly in interviews. Problems like Word Search, Unique Paths III, and Longest Increasing Path in a Matrix all require you to explore paths on a grid while managing visited state. Path with Maximum Gold strips away the extra complexity and gives you the core pattern in its purest form: try every starting cell, explore all possible paths from that cell, and track the maximum.

The key challenge is not finding a path. It is finding the best path. You cannot use BFS or greedy here because the optimal path might twist and turn through the grid in ways that a greedy approach would never consider. You need to try every valid path, which means backtracking.

The key insight

You must try starting from every cell that has gold, because the optimal path might begin anywhere. From each starting cell, you run DFS and explore all four directions. When you visit a cell, you temporarily mark it as visited so you do not loop back to it. When you finish exploring from that cell, you unmark it so other paths can use it. This "mark, explore, unmark" pattern is the heart of backtracking.

The algorithm:

1. For each cell with gold, start a DFS from that cell.
2. At each cell, add the gold to the running total. Mark the cell as visited (set it to 0).
3. Recursively explore all four neighbors that have gold and are not visited.
4. Track the maximum gold seen across all recursive calls.
5. Unmark the cell (restore its original value) before returning.

The solution

def getMaximumGold(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])

    def backtrack(r, c):
        gold = grid[r][c]
        grid[r][c] = 0
        best = 0

        for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] > 0:
                best = max(best, backtrack(nr, nc))

        grid[r][c] = gold
        return gold + best

    result = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] > 0:
                result = max(result, backtrack(r, c))

    return result

Let's walk through what each piece does.

The outer loop iterates over every cell in the grid. For each cell that contains gold, we launch a backtracking DFS. This ensures we try every possible starting point.

The backtrack function does three things. First, it saves the current cell's gold and marks the cell as visited by setting it to 0. Second, it explores all four neighbors, recursing into any neighbor that has gold. Each recursive call returns the maximum gold collectible from that neighbor onward. We take the best result. Third, it restores the cell's original value before returning. That restore step is the "unchoose" in choose-explore-unchoose, and it is what makes this backtracking rather than a simple DFS.

The return value of backtrack(r, c) is the gold at cell (r, c) plus the best gold collectible from any path extending from (r, c). The outer loop tracks the maximum across all starting cells.

Visual walkthrough

Let's trace through a 3x3 grid to see how backtracking explores and abandons paths. The grid has gold at five cells and zeros at the four corners.

Notice how the algorithm backtracks after hitting dead ends. When it reaches (0,1) and finds no unvisited neighbors with gold, it returns to (1,1) and tries the next direction. The "unmark" step after each recursive call is what allows cells to be revisited by different paths starting from different neighbors. Without it, the first path explored would permanently consume cells, and later paths would miss them.

Complexity analysis

Time is O(4^k) in the worst case, where k is the number of cells with gold. At each cell, you branch into up to 4 directions, and the maximum path length is k. In practice, the visited marking prunes most branches, so runtime is much better than the theoretical worst case. The constraint that grid dimensions are at most 15x15 keeps this tractable.

Space is O(m * n) for the recursion stack. The deepest the recursion can go is the number of gold cells, which is at most m * n. We reuse the grid itself for visited marking, so no extra data structure is needed.

The building blocks

1. Grid backtracking with in-place visited marking

The pattern of using the grid itself to track visited state:

def backtrack(r, c):
    original = 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 < rows and 0 <= nc < cols and grid[nr][nc] > 0:
            backtrack(nr, nc)
    grid[r][c] = original

This eliminates the need for a separate visited set. You save the cell value, set it to a sentinel (0 in this case), explore, and restore. The same pattern appears in Word Search (where you temporarily replace the character with #) and Unique Paths III (where you decrement a counter). Any time you need DFS on a grid with backtracking, this is the template.

2. Multi-start DFS

The pattern of launching DFS from every valid starting cell:

result = 0
for r in range(rows):
    for c in range(cols):
        if grid[r][c] > 0:
            result = max(result, backtrack(r, c))

Unlike problems where you know the starting point (like a maze with a single entrance), Path with Maximum Gold requires trying every cell as a potential start. You iterate over all cells, skip the zeros, and keep the best result. This same multi-start approach appears in Number of Islands (where each unvisited land cell starts a new DFS) and Longest Increasing Path (where each cell is a potential starting point for an increasing path).

Edge cases

Before submitting, think through these scenarios:

• Single cell with gold: the grid is 1x1 with a positive value. Return that value.
• All zeros: every cell is 0. No valid starting cell exists. Return 0.
• All cells have gold: every cell is positive. The optimal path visits every cell. The answer is the sum of all values.
• Linear path: gold cells form a single line with no branching. Only one path exists. Backtracking still works but never actually backtracks.
• Disconnected gold regions: gold cells form separate islands. You try starting from each island and return the best result across all of them.
• Grid is 1 x n or m x 1: a single row or column. The path can only go left/right or up/down.

From understanding to recall

You have seen how grid backtracking works: save the cell, mark visited, explore neighbors, restore the cell. The logic is clean and the code is short. But writing it from scratch under time pressure is where people stumble.

The details that trip people up are subtle. Do you mark visited before or after adding the gold? Do you restore the cell before or after the recursive call? Do you return the gold plus the best neighbor, or just the best neighbor? These are not gaps in understanding. They are gaps in recall, and they cost people offers.

Spaced repetition is how you close them. You practice writing the grid backtracking template, the in-place visited marking, and the multi-start loop from memory at increasing intervals. After a few rounds, the pattern is automatic. You see "find the best path through a grid" in a problem description, and the backtracking template flows out without hesitation.

Related posts

• Number of Islands - Grid DFS fundamentals where you flood-fill connected components
• Word Search - Another backtracking on a grid problem that uses the same in-place visited marking
• N-Queens - Classic backtracking with constraint checking on a board

CodeBricks breaks Path with Maximum Gold into its grid backtracking and multi-start DFS building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a grid backtracking problem shows up in your interview, you do not think about it. You just write it.