Skip to main content

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:

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

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.

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:

  1. Try each starting cell:

    • For each cell with gold (value > 0), start a DFS
    • This ensures we find the optimal starting position

  2. 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

  3. 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

  4. 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