Path with Maximum Gold

This question is asked by Amazon. Given a 2D matrix that represents a gold mine, where each cell's value represents an amount of gold, return the maximum amount of gold you can collect given the following rules:

You may start and stop collecting gold from any position
You can never visit a cell that contains 0 gold
You cannot visit the same cell more than once
From the current cell, you may walk one cell to the left, right, up, or down

Example(s)

Example 1:

Input: goldMine = [
    [0, 2, 0],
    [8, 6, 3],
    [0, 9, 0]
]
Output: 23
Explanation:
Start at cell (1, 1) with 9 gold
Move to cell (1, 0) with 6 gold (total: 15)
Move to cell (0, 0) with 8 gold (total: 23)
Cannot move further (all neighbors are 0 or visited)
Path: 9 → 6 → 8 = 23

Example 2:

Input: goldMine = [
    [1, 0, 7],
    [2, 0, 6],
    [3, 4, 5],
    [0, 3, 0],
    [9, 0, 20]
]
Output: 28
Explanation:
Optimal path collects maximum gold from connected cells.

Example 3:

Input: goldMine = [
    [0, 6, 0],
    [5, 8, 7],
    [0, 9, 0]
]
Output: 24
Explanation:
Start at 9, collect: 9 → 8 → 7 = 24

Solution

The solution uses DFS with Backtracking:

Try each starting cell: For each cell with gold, start a DFS
DFS exploration: Explore all paths from current cell
Backtracking: Mark/unmark visited cells
Track maximum: Keep track of maximum gold collected

JavaScript Solution
Python Solution

JavaScript Solution - DFS with Backtracking

/**
* Find maximum gold that can be collected
* @param {number[][]} goldMine - 2D matrix representing gold mine
* @return {number} - Maximum amount of gold
*/
function getMaximumGold(goldMine) {
const rows = goldMine.length;
const cols = goldMine[0].length;
let maxGold = 0;

// Directions: up, down, left, right
const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];

/**
 * DFS function to explore paths from a cell
 * @param {number} row - Current row
 * @param {number} col - Current column
 * @param {number} currentGold - Gold collected so far
 */
function dfs(row, col, currentGold) {
  // Check bounds and if cell has gold
  if (row < 0 || row >= rows || col < 0 || col >= cols || goldMine[row][col] === 0) {
    return;
  }
  
  // Collect gold from current cell
  const gold = goldMine[row][col];
  currentGold += gold;
  maxGold = Math.max(maxGold, currentGold);
  
  // Mark cell as visited (set to 0 temporarily)
  goldMine[row][col] = 0;
  
  // Explore all four directions
  for (const [dr, dc] of directions) {
    const newRow = row + dr;
    const newCol = col + dc;
    dfs(newRow, newCol, currentGold);
  }
  
  // Backtrack: restore cell value
  goldMine[row][col] = gold;
}

// Try starting from each cell that has gold
for (let i = 0; i < rows; i++) {
  for (let j = 0; j < cols; j++) {
    if (goldMine[i][j] > 0) {
      dfs(i, j, 0);
    }
  }
}

return maxGold;
}

// Test cases
console.log('Example 1:', getMaximumGold([
  [0, 2, 0],
  [8, 6, 3],
  [0, 9, 0]
])); 
// 23

console.log('Example 2:', getMaximumGold([
  [1, 0, 7],
  [2, 0, 6],
  [3, 4, 5],
  [0, 3, 0],
  [9, 0, 20]
])); 
// 28

Output:

Click "Run Code" to execute the code and see the results.

Python Solution - DFS with Backtracking

from typing import List

def get_maximum_gold(gold_mine: List[List[int]]) -> int:
  """
  Find maximum gold that can be collected
  
  Args:
      gold_mine: 2D matrix representing gold mine
      
  Returns:
      int: Maximum amount of gold
  """
  rows = len(gold_mine)
  cols = len(gold_mine[0])
  max_gold = 0
  
  # Directions: up, down, left, right
  directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
  
  def dfs(row: int, col: int, current_gold: int):
      """
      DFS function to explore paths from a cell
      
      Args:
          row: Current row
          col: Current column
          current_gold: Gold collected so far
      """
      # Check bounds and if cell has gold
      if row < 0 or row >= rows or col < 0 or col >= cols or gold_mine[row][col] == 0:
          return
      
      # Collect gold from current cell
      gold = gold_mine[row][col]
      current_gold += gold
      nonlocal max_gold
      max_gold = max(max_gold, current_gold)
      
      # Mark cell as visited (set to 0 temporarily)
      gold_mine[row][col] = 0
      
      # Explore all four directions
      for dr, dc in directions:
          new_row = row + dr
          new_col = col + dc
          dfs(new_row, new_col, current_gold)
      
      # Backtrack: restore cell value
      gold_mine[row][col] = gold
  
  # Try starting from each cell that has gold
  for i in range(rows):
      for j in range(cols):
          if gold_mine[i][j] > 0:
              dfs(i, j, 0)
  
  return max_gold

# Test cases
print('Example 1:', get_maximum_gold([
  [0, 2, 0],
  [8, 6, 3],
  [0, 9, 0]
]))  
# 23

print('Example 2:', get_maximum_gold([
  [1, 0, 7],
  [2, 0, 6],
  [3, 4, 5],
  [0, 3, 0],
  [9, 0, 20]
]))  
# 28

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Complexity

Time Complexity: O((rows × cols) × 4^K) - Where K is the maximum path length. For each starting cell, we explore all paths. In worst case, we explore 4^K paths.
Space Complexity: O(K) - For the recursion stack, where K is the maximum path length.

Approach

The solution uses DFS with Backtracking:

Try each starting cell:
- For each cell with gold (value > 0), start a DFS
- This ensures we find the optimal starting position
DFS exploration:
- From current cell, explore all four directions (up, down, left, right)
- Check bounds and if cell has gold
- Collect gold and update maximum
Backtracking:
- Mark cell as visited by setting it to 0 temporarily
- After exploring all paths from this cell, restore its value
- This allows exploring all possible paths
Track maximum:
- Keep track of maximum gold collected across all paths
- Update whenever we find a better path

Key Insights

DFS with backtracking: Explore all paths from each starting cell
Mark/unmark cells: Temporarily set to 0, then restore
Try all starting positions: Maximum might start from any cell
O(4^K) paths: Exponential but necessary to find optimal
No memoization needed: Each path is unique (can't revisit)

Step-by-Step Example

Let's trace through Example 1: goldMine = [[0,2,0], [8,6,3], [0,9,0]]

goldMine = [
    [0, 2, 0],
    [8, 6, 3],
    [0, 9, 0]
]

Try starting from each cell with gold:

Start at (0, 1): value = 2
  Collect 2, maxGold = 2
  Neighbors: (0,0)=0, (0,2)=0, (1,1)=6
  Move to (1, 1): value = 6
    Collect 6, total = 8, maxGold = 8
    Neighbors: (0,1)=0 (visited), (1,0)=8, (1,2)=3, (2,1)=9
    Move to (1, 0): value = 8
      Collect 8, total = 16, maxGold = 16
      Neighbors: (0,0)=0, (1,1)=0 (visited), (2,0)=0
      Backtrack
    Move to (1, 2): value = 3
      Collect 3, total = 11, maxGold = 16
      Neighbors: (0,2)=0, (1,1)=0 (visited), (2,2)=0
      Backtrack
    Move to (2, 1): value = 9
      Collect 9, total = 17, maxGold = 17
      Neighbors: (1,1)=0 (visited), (2,0)=0, (2,2)=0
      Backtrack
    Backtrack
  Backtrack
  maxGold = 17

Start at (1, 0): value = 8
  ... (similar exploration)
  maxGold = max(17, ...)

Start at (1, 1): value = 6
  ... (similar exploration)
  maxGold = max(17, ...)

Start at (1, 2): value = 3
  ... (similar exploration)
  maxGold = max(17, ...)

Start at (2, 1): value = 9
  Collect 9, maxGold = max(17, 9) = 17
  Neighbors: (1,1)=6, (2,0)=0, (2,2)=0
  Move to (1, 1): value = 6
    Collect 6, total = 15, maxGold = 17
    Neighbors: (0,1)=2, (1,0)=8, (1,2)=3, (2,1)=0 (visited)
    Move to (1, 0): value = 8
      Collect 8, total = 23, maxGold = 23 ✓
      Neighbors: (0,0)=0, (1,1)=0 (visited), (2,0)=0
      Backtrack
    Move to (0, 1): value = 2
      Collect 2, total = 17, maxGold = 23
      Neighbors: (0,0)=0, (0,2)=0, (1,1)=0 (visited)
      Backtrack
    Move to (1, 2): value = 3
      Collect 3, total = 18, maxGold = 23
      Neighbors: (0,2)=0, (1,1)=0 (visited), (2,2)=0
      Backtrack
    Backtrack
  Backtrack

Result: maxGold = 23

Visual Representation

Example 1: goldMine = [
    [0, 2, 0],
    [8, 6, 3],
    [0, 9, 0]
]

Optimal path starting from (2, 1):
  9 → 6 → 8 = 23

Visual:
  [0, 2, 0]
  [8, 6, 3]  ← Start at 9, go to 6, then to 8
  [0, 9, 0]  ↑
            Start here

Path: (2,1) → (1,1) → (1,0)
Values: 9 + 6 + 8 = 23

Edge Cases

All zeros: Return 0 (no gold to collect)
Single cell with gold: Return that value
Isolated cells: Each cell is its own path
Large matrix: DFS explores all paths
No valid path: Return 0

Important Notes

Can start anywhere: Try all cells with gold as starting points
Cannot visit 0 cells: Skip cells with 0 gold
Cannot revisit: Mark cells as visited during DFS
Backtracking: Restore cell values after exploration
O(4^K) paths: Exponential but necessary

Why DFS with Backtracking Works

Key insight:

We need to explore all possible paths from each starting cell
DFS systematically explores all paths
Backtracking allows exploring all paths without creating copies
Trying all starting positions ensures we find the optimal path

Optimal substructure:

Maximum gold from a cell = cell value + max gold from neighbors
But we can't use DP because paths can't revisit cells
So we use DFS to explore all unique paths

Word Search: Similar DFS with backtracking
Number of Islands: Similar matrix DFS
Max Area of Island: Similar DFS problem
Unique Paths: Different matrix problem

Takeaways

DFS with backtracking explores all paths
Try all starting positions to find optimal
Mark/unmark cells for backtracking
O(4^K) time exponential but necessary
Classic backtracking problem with matrix traversal

Example(s)​

Solution​

JavaScript Solution - DFS with Backtracking

Output:

Python Solution - DFS with Backtracking

Output:

Complexity​

Approach​

Key Insights​

Step-by-Step Example​

Visual Representation​

Edge Cases​

Important Notes​

Why DFS with Backtracking Works​

Related Problems​

Takeaways​

Example(s)

Solution

Complexity

Approach

Key Insights

Step-by-Step Example

Visual Representation

Edge Cases

Important Notes

Why DFS with Backtracking Works

Related Problems

Takeaways