{x}
blog image

Path with Maximum Gold

In a gold mine grid of size m x n, each cell in this mine has an integer representing the amount of gold in that cell, 0 if it is empty.

Return the maximum amount of gold you can collect under the conditions:

  • Every time you are located in a cell you will collect all the gold in that cell.
  • From your position, you can walk one step to the left, right, up, or down.
  • You can't visit the same cell more than once.
  • Never visit a cell with 0 gold.
  • You can start and stop collecting gold from any position in the grid that has some gold.

 

Example 1:

Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
Output: 24
Explanation:
[[0,6,0],
 [5,8,7],
 [0,9,0]]
Path to get the maximum gold, 9 -> 8 -> 7.

Example 2:

Input: grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
Output: 28
Explanation:
[[1,0,7],
 [2,0,6],
 [3,4,5],
 [0,3,0],
 [9,0,20]]
Path to get the maximum gold, 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7.

 

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 15
  • 0 <= grid[i][j] <= 100
  • There are at most 25 cells containing gold.

Solution Explanation: Path with Maximum Gold

This problem asks to find the maximum amount of gold that can be collected by traversing a grid, starting and ending at any cell with gold, moving only up, down, left, or right, without revisiting a cell.

Approach: Depth-First Search (DFS) with Backtracking

The most efficient approach is using Depth-First Search (DFS) along with backtracking. The algorithm iterates through each cell in the grid. If a cell contains gold (value > 0), it initiates a DFS traversal from that cell.

The DFS function works as follows:

  1. Base Case: If the current cell is out of bounds or contains no gold (value == 0), it returns 0.

  2. Recursive Step:

    • It stores the gold value of the current cell (v).
    • It sets the gold value of the current cell to 0 to mark it as visited.
    • It recursively explores the four adjacent cells (up, down, left, right).
    • It calculates the maximum gold collected by taking the current cell's gold (v) plus the maximum gold collected from the recursive calls to adjacent cells.
    • It restores the original gold value of the current cell (grid[i][j] = v)—this is crucial for backtracking; otherwise, future paths starting from other cells would be affected.
    • It returns the maximum gold collected from this cell.

The main part of the algorithm iterates through all cells of the grid. For each cell, if it contains gold, it calls the dfs function and updates the maximum gold found so far (ans).

Time Complexity Analysis

The time complexity is determined by the number of possible paths. In the worst-case scenario, the algorithm explores all possible paths starting from each cell. The branching factor is at most 4 (four directions). While the maximum path length is bounded by the total number of cells (mn), the number of possible paths can grow exponentially, especially when there are many interconnected cells with gold. Thus the upper bound is O(4k), where k is approximately mn. However, since we mark visited cells, this is significantly less than the total number of paths without any pruning. A more practical analysis would be O(m * n * 4p), where 'p' is the maximum length of a valid path through non-zero elements. Since the grid is limited to a maximum size, we can consider this to be approximately O(m * n) in many cases.

Space Complexity Analysis

The space complexity is dominated by the recursive call stack in the DFS function. In the worst-case scenario, the depth of the recursion can be proportional to the number of cells in the grid (m * n). Therefore, the space complexity is O(m * n).

Code in Different Languages

The code implementations provided in the original response are correct and efficient. They accurately reflect the described algorithm. The Python code cleverly uses pairwise from itertools to handle the directional changes compactly, while others use the more common directional array approach. The core recursive DFS structure is consistent across all languages.

The overall solution offers a well-structured and optimized approach to solving the "Path with Maximum Gold" problem.