Problem Description

You are given a 2D grid representing a gold mine where each cell contains a non-negative integer indicating the amount of gold in that cell (0 means the cell is empty).

Your task is to find the maximum amount of gold you can collect by following these rules:

• You collect all the gold from any cell you visit
• From any cell, you can move one step in four directions: left, right, up, or down
• You cannot visit the same cell twice in a single path
• You cannot enter cells that contain 0 gold
• You can start collecting gold from any cell that contains gold (value > 0)
• You can stop collecting at any point

The solution uses a depth-first search (DFS) approach with backtracking. For each possible starting cell in the grid, it explores all valid paths from that cell. During the exploration, when visiting a cell, the algorithm temporarily sets its value to 0 to mark it as visited, then recursively explores all four adjacent cells. After exploring all paths from that cell, it restores the original value (backtracking) so other paths can potentially use this cell.

The key insight is using the grid itself to track visited cells by temporarily setting visited cells to 0, which both marks them as visited and prevents re-entry (since cells with 0 gold cannot be entered). The pairwise(dirs) technique with dirs = (-1, 0, 1, 0, -1) generates the four directional moves: (-1, 0), (0, 1), (1, 0), (0, -1) representing up, right, down, and left movements respectively.

The maximum gold collected across all possible starting positions and paths is returned as the final answer.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• No: While we have a 2D grid, this isn't a traditional graph problem with explicit nodes and edges. We're looking for paths through a grid to collect gold.

Need to solve for kth smallest/largest?

• No: We're looking for the maximum total gold collected, not the kth smallest or largest value.

Involves Linked Lists?

• No: The problem uses a 2D array/grid, not linked lists.

Does the problem have small constraints?

• Yes: The problem typically has reasonable grid dimensions (m × n where both are usually ≤ 15-20), and we need to explore all possible paths from each starting position. The constraint that we can't revisit cells limits the path length, making exhaustive search feasible.

Brute force / Backtracking?

• Yes: We need to explore all possible paths from each valid starting position, trying different directions at each step. When we reach a dead end, we backtrack and try other paths. This is a classic backtracking scenario where we:
  • Make a choice (move in a direction)
  • Explore recursively from that choice
  • Undo the choice (restore the cell value) to try other options

Conclusion: The flowchart correctly leads us to use a Backtracking approach. The small constraints and need to explore all possible paths while maintaining state (visited cells) makes backtracking the ideal solution for finding the maximum gold collection path.

Intuition

When we look at this problem, we need to find the path that collects the maximum gold. Since we can start from any cell with gold and move in four directions without revisiting cells, we're essentially exploring all possible paths through the grid.

The key insight is that we don't know which starting point or which path will give us the maximum gold until we try them all. This immediately suggests an exhaustive search approach. Since the grid has small constraints and we can't revisit cells, the total number of possible paths is limited.

Why backtracking? Consider what happens when we're exploring a path:

1. We pick a cell and collect its gold
2. We need to mark this cell as "visited" so we don't come back to it
3. We explore all four directions from this cell
4. After exploring all paths from this position, we need to "un-visit" this cell so that other paths (starting from different positions) can potentially use it

This "try-undo-try again" pattern is the essence of backtracking. The clever part of the solution is using the grid itself to track visited cells - by temporarily setting a visited cell's value to 0, we both mark it as visited and prevent re-entry (since we can't enter cells with 0 gold). After exploring all paths from that cell, we restore its original value.

The algorithm naturally handles all the constraints:

• We automatically skip cells with 0 gold (empty cells)
• We prevent revisiting cells within the same path
• We try all possible starting positions
• We explore all valid moves (up, down, left, right) from each position

By trying every possible starting cell and using DFS with backtracking to explore all paths from each start, we guarantee finding the maximum gold collection possible.

Learn more about Backtracking patterns.

Solution Approach

The solution implements a DFS (Depth-First Search) with backtracking to explore all possible paths and find the maximum gold collection.

Main Function Structure: The solution starts by trying every cell in the grid as a potential starting point using a nested loop: max(dfs(i, j) for i in range(m) for j in range(n)). This ensures we don't miss the optimal starting position.

DFS Implementation: The dfs(i, j) function explores all paths starting from cell (i, j):

1. Base Case: First, we check if the current position is valid:

   if not (0 <= i < m and 0 <= j < n and grid[i][j]):
       return 0

   This returns 0 if we're out of bounds or hit a cell with 0 gold.

2. Mark as Visited: We temporarily store the gold value and set the cell to 0:

   v = grid[i][j]
   grid[i][j] = 0

   This prevents revisiting this cell in the current path.

3. Explore All Directions: The clever use of pairwise(dirs) generates the four directional moves:

   dirs = (-1, 0, 1, 0, -1)
   ans = max(dfs(i + a, j + b) for a, b in pairwise(dirs)) + v

   The pairwise function creates pairs: (-1, 0), (0, 1), (1, 0), (0, -1), representing moves up, right, down, and left respectively. We recursively explore each direction and take the maximum gold collected from all four paths.

4. Backtrack: After exploring all paths from this cell, we restore its original value:

   grid[i][j] = v
   return ans

   This allows other paths (from different starting points) to potentially use this cell.

Time Complexity: O(m * n * 4^k) where k is the maximum path length (at most m * n). For each starting cell, we explore up to 4 directions at each step.

Space Complexity: O(k) for the recursion stack depth, where k is the maximum path length. The solution cleverly uses the input grid itself for tracking visited cells, avoiding extra space for a visited array.

The algorithm guarantees finding the maximum gold by exhaustively trying all starting positions and all possible paths from each position, using backtracking to ensure we explore every valid combination.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider this 3×3 grid:

[[1, 2, 3],
 [0, 4, 0],
 [7, 0, 9]]

Step 1: Try each cell as starting point

Let's trace through starting from cell (0,1) which contains gold value 2:

From (0,1) with value 2:

• Mark cell as visited: grid[0][1] = 0

• Current gold collected: 2

• Try all 4 directions:

  • Up: Out of bounds → return 0
  • Right: Move to (0,2) with value 3
    • Mark (0,2) as visited: grid[0][2] = 0
    • Current gold: 3
    • Try all 4 directions from (0,2):
      • Up: Out of bounds → 0
      • Right: Out of bounds → 0
      • Down: (1,2) has value 0 → 0
      • Left: (0,1) has value 0 (visited) → 0
    • Max from (0,2) = 3
    • Restore grid[0][2] = 3
  • Down: Move to (1,1) with value 4
    • Mark (1,1) as visited: grid[1][1] = 0
    • Current gold: 4
    • Try all 4 directions from (1,1):
      • Up: (0,1) has value 0 (visited) → 0
      • Right: (1,2) has value 0 → 0
      • Down: (2,1) has value 0 → 0
      • Left: (1,0) has value 0 → 0
    • Max from (1,1) = 4
    • Restore grid[1][1] = 4
  • Left: Move to (0,0) with value 1
    • Mark (0,0) as visited: grid[0][0] = 0
    • Current gold: 1
    • Try all 4 directions from (0,0):
      • All lead to boundaries or visited/empty cells → 0
    • Max from (0,0) = 1
    • Restore grid[0][0] = 1

• Maximum from adjacent cells = max(3, 4, 1) = 4

• Total from starting at (0,1) = 2 + 4 = 6

• Restore grid[0][1] = 2

Now let's trace a better path starting from (2,0) with value 7:

From (2,0) with value 7:

• Mark cell as visited: grid[2][0] = 0
• Current gold: 7
• Try all 4 directions:
  • Up: (1,0) has value 0 → 0
  • Right: (2,1) has value 0 → 0
  • Down: Out of bounds → 0
  • Left: Out of bounds → 0
• Max from adjacent = 0
• Total from (2,0) = 7 + 0 = 7
• Restore grid[2][0] = 7

The optimal path starts from (2,2) with value 9:

From (2,2) with value 9:

• Mark as visited: grid[2][2] = 0
• Current gold: 9
• Try all 4 directions:
  • Up: (1,2) has value 0 → 0
  • Right: Out of bounds → 0
  • Down: Out of bounds → 0
  • Left: (2,1) has value 0 → 0
• Max from adjacent = 0
• Total from (2,2) = 9 + 0 = 9
• Restore grid[2][2] = 9

After trying all starting positions, the algorithm finds that the maximum gold collection is 9 (starting from cell (2,2) and collecting only that cell's gold since it's surrounded by empty cells or boundaries).

Note how the backtracking works: after exploring paths from a cell, we restore its original value so other starting points can potentially use it. This ensures we explore all possible paths without missing any combinations.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n × 4^k), where m is the number of rows, n is the number of columns, and k is the maximum path length (at most min(m × n, 25) since each cell has at most 25 gold).

The analysis works as follows:

• We try starting DFS from each of the m × n cells
• From each cell, we explore up to 4 directions (up, down, left, right)
• At each step in the path, we have at most 3 valid directions to continue (we can't go back to where we came from due to the cell being temporarily set to 0)
• The maximum depth of recursion is k, which represents the longest possible path of cells with gold
• This gives us O(m × n × 4 × 3^(k-1)) which simplifies to O(m × n × 3^k) for practical purposes

Note: The reference answer states O(m × n × 3^k) which accounts for the fact that after the first move, we effectively have only 3 directions to explore (excluding the direction we came from).

Space Complexity: O(k), where k is the maximum recursion depth.

The space complexity comes from:

• The recursion call stack which can go up to depth k in the worst case
• Since we modify the grid in-place (setting visited cells to 0 temporarily and restoring them), we don't use additional space proportional to the grid size
• The maximum recursion depth k is bounded by the total number of non-zero cells in the grid, which is at most m × n

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Restore the Grid Value (Backtracking)

One of the most common mistakes is forgetting to restore the original cell value after exploring all paths from that cell. This leads to permanently marking cells as visited (value = 0), which prevents other starting paths from using those cells.

Incorrect Implementation:

def dfs(row, col):
    if not (0 <= row < rows and 0 <= col < cols and grid[row][col] > 0):
        return 0
  
    current_gold = grid[row][col]
    grid[row][col] = 0  # Mark as visited
  
    max_neighbor_gold = 0
    for direction_idx in range(4):
        next_row = row + directions[direction_idx]
        next_col = col + directions[direction_idx + 1]
        max_neighbor_gold = max(max_neighbor_gold, dfs(next_row, next_col))
  
    # MISTAKE: Forgot to restore grid[row][col] = current_gold
    return current_gold + max_neighbor_gold

Why This Fails:

• After the first DFS call completes, many cells are permanently set to 0
• Subsequent starting positions cannot explore paths through these cells
• Results in incorrect (lower) maximum gold values

Correct Solution: Always restore the original value before returning:

grid[row][col] = current_gold  # Restore original value
return current_gold + max_neighbor_gold

2. Incorrect Direction Array Indexing

Another common pitfall is misunderstanding how the direction array works with the indexing pattern.

Incorrect Implementation:

# Wrong: Using separate arrays
directions_row = [-1, 0, 1, 0]
directions_col = [0, 1, 0, -1]

for i in range(4):
    next_row = row + directions_row[i]
    next_col = col + directions_col[i]
    # ...

While this works, it's more error-prone. The single array approach [-1, 0, 1, 0, -1] is cleaner but requires understanding that we access pairs using indices [i] and [i+1].

Common Mistake:

directions = [-1, 0, 1, 0, -1]
for i in range(5):  # WRONG: Should be range(4)
    next_row = row + directions[i]
    next_col = col + directions[i + 1]  # This will go out of bounds when i=4

3. Not Checking for Empty Grid or All-Zero Grid

While the current solution handles this correctly through the DFS base case, developers sometimes add unnecessary edge case checks that can introduce bugs:

Unnecessary and Error-Prone:

def getMaximumGold(self, grid):
    if not grid or not grid[0]:  # Unnecessary if problem guarantees valid grid
        return 0
  
    # Check if all cells are 0 - unnecessary overhead
    has_gold = False
    for row in grid:
        if any(cell > 0 for cell in row):
            has_gold = True
            break
    if not has_gold:
        return 0

The DFS naturally handles these cases - if all cells are 0 or the grid is empty, the DFS will return 0 for all starting positions.

4. Using a Separate Visited Set

Some developers use a separate visited set instead of modifying the grid, which works but is less efficient:

Less Efficient Approach:

def dfs(row, col, visited):
    if (row, col) in visited or not (0 <= row < rows and 0 <= col < cols) or grid[row][col] == 0:
        return 0
  
    visited.add((row, col))
    # explore neighbors...
    visited.remove((row, col))  # Don't forget to remove!

Issues:

• Extra space complexity O(k) for the visited set
• Need to pass visited set through all recursive calls
• Slower due to set operations
• Easy to forget to remove from visited set when backtracking

The grid modification approach is cleaner and more efficient since we're already checking grid[row][col] > 0 as a condition.