LeetCode 1219 - Path with Maximum Gold

Difficulty: 🟡 Medium
Topics: Array, Backtracking, Matrix

Solution

Problem Understanding

The problem gives us a two dimensional grid representing a gold mine. Each cell contains either a positive amount of gold or 0, which means the cell is empty. We are allowed to start from any cell that contains gold and move through the grid collecting gold along the way.

Movement is restricted to the four cardinal directions, up, down, left, and right. We are not allowed to move diagonally. Once we visit a cell, we cannot visit it again during the same path. We are also forbidden from entering cells that contain 0.

The goal is to determine the maximum amount of gold that can be collected from any valid path.

A key detail is that we may start and stop anywhere, as long as the starting cell contains gold. This means we must consider every gold cell as a potential starting point.

The constraints strongly influence the expected solution strategy:

The grid dimensions can be as large as 15 x 15
However, there are at most 25 cells containing gold

This second constraint is the most important observation. Even though the grid itself can contain up to 225 cells, only a small number are actually traversable. This makes exhaustive exploration with pruning feasible.

Some important edge cases include:

A grid with only one gold cell
A grid where all cells are 0
Multiple disconnected gold regions
Paths where greedily taking the largest adjacent gold value does not lead to the optimal total
Cycles formed by gold cells, which require careful visited tracking to avoid revisiting cells

The problem guarantees that movement is only between valid grid cells and that gold values are non negative integers.

Approaches

Brute Force Approach

A brute force solution would try every possible path starting from every gold cell. At each step, the algorithm would recursively attempt to move in all four directions while keeping track of visited cells.

This approach is correct because it explores every valid path and computes the gold collected for each one. The maximum among all explored paths must therefore be the optimal answer.

However, the number of possible paths grows exponentially. If there are k gold cells, each recursive call may branch into up to four directions. In the worst case, this produces approximately O(4^k) recursive states.

Although the constraint of at most 25 gold cells keeps this from becoming completely infeasible, naive recursion without pruning or backtracking optimizations would still perform unnecessary repeated work.

Optimal Approach, Backtracking Depth First Search

The key observation is that the number of gold containing cells is small. Since each path cannot revisit a cell, every path corresponds to a unique traversal through the gold cells.

This naturally suggests a backtracking depth first search approach.

For each gold cell:

Start a DFS traversal
Mark the current cell as visited
Explore all valid neighboring gold cells
Compute the maximum gold obtainable from each continuation
Backtrack by unmarking the cell

Backtracking is ideal here because the visited state changes dynamically during recursive exploration. After exploring one branch, we must restore the grid state so other paths can reuse the same cells.

The algorithm efficiently enumerates all valid paths while ensuring correctness through recursive exploration.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(4^k)	O(k)	Explores every possible path without optimization
Optimal	O(4^k)	O(k)	Backtracking DFS with efficient visited handling

Here, k represents the number of gold containing cells, with k <= 25.

Algorithm Walkthrough

Store the grid dimensions in variables rows and cols.
Define the four possible movement directions:

Up
Down
Left
Right

Create a recursive DFS function that accepts the current row and column.
Inside the DFS function:

Store the current cell's gold value
Temporarily mark the cell as visited by setting its value to 0
Initialize a variable to track the best gold collectible from neighboring paths

Explore all four neighboring cells:

Compute the neighbor coordinates
Check boundary conditions
Ensure the neighboring cell contains gold
Recursively compute the maximum gold from that neighbor

After exploring all directions:

Restore the original gold value in the current cell
Return the current cell's gold plus the best neighboring result

In the main function:

Iterate through every cell in the grid
If the cell contains gold, start a DFS from that cell
Track the maximum result across all starting positions

Return the global maximum gold collected.

Why it works

The DFS explores every valid path exactly as defined by the problem constraints. Since cells are marked visited during recursion, no path can revisit the same cell. Backtracking restores the grid state after each recursive branch, ensuring independent exploration of all possibilities. Because every starting position and every valid continuation are examined, the algorithm is guaranteed to find the maximum possible gold collection.

Python Solution

from typing import List

class Solution:
    def getMaximumGold(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])

        directions = [
            (1, 0),
            (-1, 0),
            (0, 1),
            (0, -1)
        ]

        def dfs(row: int, col: int) -> int:
            current_gold = grid[row][col]

            # Mark as visited
            grid[row][col] = 0

            best_next = 0

            for dr, dc in directions:
                new_row = row + dr
                new_col = col + dc

                if (
                    0 <= new_row < rows
                    and 0 <= new_col < cols
                    and grid[new_row][new_col] > 0
                ):
                    best_next = max(
                        best_next,
                        dfs(new_row, new_col)
                    )

            # Backtrack
            grid[row][col] = current_gold

            return current_gold + best_next

        maximum_gold = 0

        for row in range(rows):
            for col in range(cols):
                if grid[row][col] > 0:
                    maximum_gold = max(
                        maximum_gold,
                        dfs(row, col)
                    )

        return maximum_gold

The implementation begins by storing the grid dimensions and defining the four movement directions. These directions simplify neighbor traversal during DFS.

The recursive dfs function performs the core backtracking logic. The current cell's gold is saved before temporarily setting the cell to 0. This acts as an in place visited marker and avoids needing an additional visited matrix.

The function then explores every valid neighboring gold cell. For each neighbor, it recursively computes the maximum gold collectible from that point onward.

After all neighbors are processed, the original gold value is restored. This backtracking step is critical because other DFS paths may later reuse this cell.

Finally, the main loop starts DFS from every gold containing cell and keeps track of the overall maximum result.

Go Solution

func getMaximumGold(grid [][]int) int {
	rows := len(grid)
	cols := len(grid[0])

	directions := [][]int{
		{1, 0},
		{-1, 0},
		{0, 1},
		{0, -1},
	}

	var dfs func(int, int) int

	dfs = func(row int, col int) int {
		currentGold := grid[row][col]

		// Mark as visited
		grid[row][col] = 0

		bestNext := 0

		for _, dir := range directions {
			newRow := row + dir[0]
			newCol := col + dir[1]

			if newRow >= 0 &&
				newRow < rows &&
				newCol >= 0 &&
				newCol < cols &&
				grid[newRow][newCol] > 0 {

				candidate := dfs(newRow, newCol)

				if candidate > bestNext {
					bestNext = candidate
				}
			}
		}

		// Backtrack
		grid[row][col] = currentGold

		return currentGold + bestNext
	}

	maximumGold := 0

	for row := 0; row < rows; row++ {
		for col := 0; col < cols; col++ {
			if grid[row][col] > 0 {
				candidate := dfs(row, col)

				if candidate > maximumGold {
					maximumGold = candidate
				}
			}
		}
	}

	return maximumGold
}

The Go implementation closely mirrors the Python version. One notable difference is the use of function variables for recursion, since anonymous recursive functions in Go must first be declared before assignment.

Go slices are used for storing movement directions. Integer overflow is not a concern because the maximum possible gold is limited to 25 * 100 = 2500, which easily fits within Go's integer range.

The backtracking logic is identical, with the current cell temporarily set to 0 and later restored.

Worked Examples

Example 1

grid = [
  [0,6,0],
  [5,8,7],
  [0,9,0]
]

The algorithm starts DFS from every gold cell.

Starting from cell `(0,1)` with value `6`

Step	Current Path	Gold Collected
Start	6	6
Move Down	6 → 8	14
Move Right	6 → 8 → 7	21

This path ends because no further moves are possible.

Alternative branch

Step	Current Path	Gold Collected
Start	6	6
Move Down	6 → 8	14
Move Left	6 → 8 → 5	19

Best path from another start

Starting from 9:

Step	Current Path	Gold Collected
Start	9	9
Move Up	9 → 8	17
Move Right	9 → 8 → 7	24

Maximum result becomes 24.

Example 2

grid = [
  [1,0,7],
  [2,0,6],
  [3,4,5],
  [0,3,0],
  [9,0,20]
]

The optimal path is:

1 → 2 → 3 → 4 → 5 → 6 → 7

Path trace

Step	Current Path	Running Total
1	1	1
2	1 → 2	3
3	1 → 2 → 3	6
4	1 → 2 → 3 → 4	10
5	1 → 2 → 3 → 4 → 5	15
6	1 → 2 → 3 → 4 → 5 → 6	21
7	1 → 2 → 3 → 4 → 5 → 6 → 7	28

No other valid path yields more than 28.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(4^k)	Each gold cell may branch into four recursive directions
Space	O(k)	Recursive call stack depth is bounded by gold cells

The time complexity is exponential because the algorithm potentially explores every valid path through the gold containing cells. However, the constraint limiting gold cells to at most 25 keeps the search manageable.

The space complexity comes primarily from the recursion stack. Since no path can revisit a cell, the maximum recursion depth is at most k.

Test Cases

from typing import List

class Solution:
    def getMaximumGold(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        def dfs(row: int, col: int) -> int:
            current = grid[row][col]
            grid[row][col] = 0

            best = 0

            for dr, dc in directions:
                nr = row + dr
                nc = col + dc

                if (
                    0 <= nr < rows
                    and 0 <= nc < cols
                    and grid[nr][nc] > 0
                ):
                    best = max(best, dfs(nr, nc))

            grid[row][col] = current

            return current + best

        answer = 0

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

        return answer

solver = Solution()

# Example 1
assert solver.getMaximumGold([
    [0,6,0],
    [5,8,7],
    [0,9,0]
]) == 24

# Example 2
assert solver.getMaximumGold([
    [1,0,7],
    [2,0,6],
    [3,4,5],
    [0,3,0],
    [9,0,20]
]) == 28

# Single gold cell
assert solver.getMaximumGold([
    [10]
]) == 10

# All zero grid
assert solver.getMaximumGold([
    [0,0],
    [0,0]
]) == 0

# Linear connected path
assert solver.getMaximumGold([
    [1,2,3,4]
]) == 10

# Disconnected regions
assert solver.getMaximumGold([
    [1,0,10],
    [0,0,0],
    [5,0,7]
]) == 10

# Path requires avoiding greedy choice
assert solver.getMaximumGold([
    [1,100],
    [2,3]
]) == 106

# Multiple branching possibilities
assert solver.getMaximumGold([
    [1,2,3],
    [0,4,0],
    [7,6,5]
]) == 28

Test	Why
Example 1	Validates standard branching traversal
Example 2	Validates longer optimal path
Single gold cell	Tests smallest non empty case
All zero grid	Ensures algorithm handles no valid starts
Linear connected path	Tests simple path accumulation
Disconnected regions	Ensures independent regions are considered
Greedy trap case	Verifies exhaustive search correctness
Multiple branching possibilities	Tests deeper recursive exploration

Edge Cases

One important edge case occurs when the grid contains only 0 values. In this situation, there are no valid starting positions. A naive implementation might incorrectly attempt DFS from every cell or fail because no traversal occurs. The implementation handles this naturally because DFS is only started from cells with gold greater than zero. The final answer therefore remains 0.

Another important case is a grid with a single gold cell. Since there are no neighboring cells to explore, the DFS should immediately return that cell's value. The recursive structure correctly handles this because the neighbor exploration loop finds no valid moves and simply returns the current gold amount.

A more subtle edge case involves cycles formed by connected gold cells. Without proper visited tracking, the DFS could revisit the same cell infinitely or count its gold multiple times. The implementation prevents this by temporarily setting visited cells to 0. Because valid moves require positive gold values, revisiting becomes impossible during the current path.

Another tricky scenario occurs when the locally largest neighboring gold value does not produce the globally optimal solution. A greedy algorithm would fail in such cases. Since this implementation explores all valid paths through backtracking DFS, it correctly identifies the true maximum total regardless of local choices.