Domain 2MediumMEDIUM

Path with Maximum Gold

LeetCode problem 1219: Path with Maximum Gold (medium).

Domain: medium•Updated: 2026-09-10
#Backtracking

Problem Breakdown

We are given an m x n 2D integer array representing a gold mine where each cell contains either gold or is empty (0). Our goal is to find the maximum amount of gold we can collect. We start at any non-zero cell and move up, down, left, or right. Crucially:

  1. No revisiting: Once you step on a cell in your current path, it cannot be visited again during that specific traversal (prevents cycles).
  2. Empty cells are walls: We can never enter a 0 value cell.
  3. Flexible Start/Stop: The optimal path doesn’t have to start at (0,0) or end there; we scan all potential starting points with gold > 0.

Inputs: A list of lists (grid) containing integers between 0 and 100. Dimensions up to 15 x 15. Output: An integer representing the maximum sum collected in a single valid path. Tricky Constraints: The grid is small, but dense backtracking can be slow (O(4N)O(4^{N})). However, there are at most 25 cells with gold. This sparsity is the key to performance; we only traverse nodes that contain value > 0.

Intuition

This problem asks for a path in an undirected graph where edges exist between adjacent non-zero cells and node weights sum up along the path without cycles (simple paths).

  1. Brute Force: Try every cell as a start point, then try all permutations of neighbors to find the longest weighted simple path. This is essentially finding the maximum weight Hamiltonian Path on subgraphs induced by gold nodes.
  2. Why Brute Force Fails: A naive DFS without pruning would explore O(4m⋅n)O(4^{m \cdot n}) states in a dense grid, which TLEs (Time Limit Exceeded). However, since we can’t step on 0 and there are at most 25 gold nodes, the effective search space is bounded by permutations of these sparse nodes.
  3. Optimal Approach: Use Depth-First Search (DFS) with Backtracking. For every cell containing gold:
    • Treat it as a starting point for a path.
    • Mark current cell as visited to prevent cycles in the current recursion stack.
    • Recursively explore valid neighbors (up, down, left, right).
    • Backtrack: Before returning from the recursive call, restore the grid value so other paths can utilize this gold later. This avoids allocating a separate visited matrix for every start node.

Approach

  1. Initialize a global or closure-scoped variable max_gold = 0.
  2. Iterate through every cell (i, j) in the grid:
    • If grid[i][j] > 0, initiate a DFS from this position to find paths starting here.
  3. Define the recursive helper function dfs(r, c):
    • Base Case: Return current accumulated gold sum (though we usually update an outer max).
    • Mark Visited: Temporarily set grid[r][c] = 0 to mark as visited for this specific path. This modifies the input in-place which is efficient but requires restoration later.
    • Explore Neighbors: For each direction (dr, dc):
      • Check bounds (r + dr, c + dc).
      • Ensure neighbor has gold (grid[r+dr][c+dc] > 0).
      • Recurse: current_gold = dfs(new_r, new_c) (or simply accumulate in the loop).
    • Backtrack: Restore grid[r][c] to its original value before returning. This allows other paths starting from different points or branches to use this cell again.
  4. Update max_gold with the result of each DFS traversal.
  5. Return max_gold.

Complexity Analysis

  • Time Complexity: O(3k)O(3^{k}) where kk is the number of cells containing gold (at most 25). In a grid, from any cell you have at most 4 neighbors; since we came from one direction and can’t go back immediately in DFS without revisiting logic, effective branching factor reduces. Given the constraint that there are only ≤25\le 25 non-zero nodes, this exponential complexity is well within limits for typical time constraints (usually ~10^8 operations per second).
  • Space Complexity: O(k)O(k) where kk is the number of gold cells in the recursion stack. In the worst case path length equals the total count of gold cells. We do not use extra space for a visited set if we modify the grid, but technically modifying input might be considered side-effect dependent; however, standard backtracking solutions often accept this trade-off or pass the visited state via arguments to save O(m⋅n)O(m \cdot n) stack overhead compared to allocating new sets at every step.

Solution

class Solution:
    def getMaximumGold(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        # Helper function for DFS backtracking
        def dfs(r, c):
            current_gold = 0
            
            # Mark cell as visited by setting gold to 0 temporarily
            temp_val = grid[r][c]
            grid[r][c] = 0 
            
            max_path_from_here = 0
            
            # Explore all valid directions: up, down, left, right
            for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                nr, nc = r + dr, c + dc
                
                if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] > 0:
                    max_path_from_here += dfs(nr, nc)
            
            # Backtrack: Restore the gold value for other paths to use this cell later
            grid[r][c] = temp_val
            
            return current_gold + max_path_from_here

        global_max = 0
        
        # Iterate over every cell as a potential starting point
        for r in range(m):
            for c in range(n):
                if grid[r][c] > 0:
                    # Start DFS from this gold-containing cell
                    current_total_gold = dfs(r, c) + grid[r][c] 
                    
                    # Note: The logic above accumulates inside the loop. 
                    # To simplify accumulation without double counting in recursion structure:
                    pass
        
        # Refining the helper to return sum correctly including start node
        def backtrack(r, c):
            current_gold = 0
            
            # Temporarily mark as visited (set to 0)
            grid[r][c] = 0 
            
            max_val = 0
            
            for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                nr, nc = r + dr, c + dc
                
                if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] > 0:
                    max_val += backtrack(nr, nc)
            
            # Restore original value for backtracking purposes
            grid[r][c] = temp_gold
            
            return current_gold + max_val

        global_max = 0
        
        def dfs(r, c):
            gold_collected = 0
            # Mark visited by setting to 0 temporarily
            saved_val = 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 < m and 0 <= nc < n and grid[nr][nc] > 0:
                    gold_collected += dfs(nr, nc)
            
            # Restore the cell value before returning (backtracking step)
            grid[r][c] = saved_val
            
            return gold_collected + saved_val

        for r in range(m):
            for c in range(n):
                if grid[r][c] > 0:
                    global_max = max(global_max, dfs(r, c))
                    
        return global_max