# Path with Maximum Gold
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/path-with-maximum-gold)
Canonical: https://scaleengineer.com/dsa/problems/path-with-maximum-gold
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Data structures:** Array, Matrix
**Companies:** [Geico](https://scaleengineer.com/companies/geico)
---
## Problem
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.

# Approaches
## Brute-Force with Path Permutations
This approach involves generating all possible sequences of gold cells and checking if they form a valid path. It's a straightforward but highly inefficient method. We first identify all cells with gold. Then, we generate all permutations of these cells. For each permutation, we check all its prefixes to see if they constitute a valid path (i.e., consecutive cells are adjacent in the grid). If a path is valid, we compute its total gold and update our maximum. This method is too slow for the given constraints due to the factorial growth in the number of permutations.
**Time:** O(m*n + k! * k^2), where `m` and `n` are the grid dimensions and `k` is the number of gold cells. The `k!` term comes from generating all permutations, making this approach impractical. · **Space:** O(k^2) to store gold cell locations and potentially an adjacency matrix for efficient checks. The space to hold a single permutation is O(k).
**Pros:** Conceptually simple to understand.
**Cons:** Extremely high time complexity (O(k!)), making it infeasible for `k` larger than about 10.; Complex to implement correctly.
### Explanation
The brute-force algorithm proceeds as follows:
1.  **Find Gold Cells**: Traverse the entire `m x n` grid to locate all cells with gold. Store their coordinates and values, say in a list of `k` cells.
2.  **Generate Permutations**: Generate all possible orderings (permutations) of these `k` cells. There are `k!` such permutations.
3.  **Validate Paths and Calculate Gold**: For each permutation, we must treat it as a potential path. Since a path can start and stop anywhere, we must check every prefix of the permutation.
    *   For a prefix of length `L`, we verify if it's a valid path. This means checking that for each `i` from 0 to `L-2`, the cell at index `i` in the sequence is adjacent (up, down, left, or right) to the cell at index `i+1`.
    *   If the prefix is a valid path, we sum the gold values of the cells in it.
    *   We keep track of the maximum sum found across all valid paths from all permutations.
4.  **Return Maximum**: After exhausting all possibilities, the maximum sum recorded is the answer.

This approach is not practical due to its factorial time complexity. For `k=25`, `25!` is an astronomically large number, making the computation impossible.
### Algorithm
*   Identify all `k` cells with gold in the grid.
*   Generate all `k!` permutations of these gold cells.
*   For each permutation, iterate through all its prefixes (from length 1 to `k`).
*   For each prefix, check if it forms a valid path by ensuring all consecutive cells are adjacent.
*   If the path is valid, calculate the sum of gold and update the global maximum.
*   Return the global maximum after checking all possibilities.

## Backtracking using Depth-First Search (DFS)
A more practical and efficient approach is to use backtracking, implemented with a Depth-First Search (DFS). The idea is to treat the grid as a graph where cells with gold are nodes. We explore all possible paths starting from every gold cell. To avoid using a cell more than once in a single path, we mark it as visited (e.g., by temporarily setting its gold value to 0) before exploring its neighbors, and then we backtrack by restoring its value after the exploration is complete. This allows the cell to be part of other paths. The maximum gold found across all starting points is the answer.
**Time:** O(m*n * 4^k), where `k` is the number of cells with gold. We can start a search from each of the `m*n` cells. From each cell, the DFS explores paths of maximum length `k`. While the worst-case is exponential, the practical performance is much better because the grid structure, boundaries, and already-visited cells heavily prune the search space. A tighter bound might be O(k * 3^k) if we only start from the `k` gold cells. · **Space:** O(k), where `k` is the number of gold cells. The space is dominated by the recursion stack depth. In the worst case, the recursion can go as deep as the number of gold cells. By modifying the grid in-place to mark visited cells, we avoid using extra space for a `visited` set.
**Pros:** Significantly more efficient than brute-force.; Low space complexity (O(k)).; Relatively straightforward to implement with recursion.
**Cons:** Time complexity is still exponential in the worst-case, which could be slow for dense grids with many gold cells.; The performance depends on the structure of the gold cells in the grid.
### Explanation
This approach uses a recursive DFS function to explore all valid paths. We can start a path from any cell with gold.

The algorithm is as follows:
1.  Initialize a global variable `maxGold = 0`.
2.  Iterate through every cell `(i, j)` in the grid. If a cell `grid[i][j]` contains gold, it's a potential starting point for a path.
3.  For each such starting cell, call a recursive DFS helper function, `dfs(grid, i, j)`, which calculates the maximum gold obtainable from a path starting at `(i, j)`.
4.  Update `maxGold = Math.max(maxGold, result_of_dfs)`. 
5.  The `dfs(grid, r, c)` function works as follows:
    *   It checks for base cases: if the cell `(r, c)` is outside the grid boundaries or contains 0 gold, the path ends, so it returns 0.
    *   It saves the gold amount of the current cell, `currentGold = grid[r][c]`.
    *   To prevent cycles and reusing the same cell in the current path, it marks the cell as visited by setting `grid[r][c] = 0`.
    *   It then recursively explores the four neighbors (up, down, left, right), and finds the maximum gold that can be collected from these subsequent paths.
    *   After the recursive calls return, it backtracks by restoring the cell's original gold value, `grid[r][c] = currentGold`. This is crucial, as the cell must be available for other paths starting from different initial cells.
    *   Finally, it returns the total gold for the current path segment: `currentGold` plus the maximum gold collected from its neighbors.

After checking all possible starting cells, `maxGold` will hold the final answer.

```java
class Solution {
    public int getMaximumGold(int[][] grid) {
        int maxGold = 0;
        int m = grid.length;
        int n = grid[0].length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] > 0) {
                    maxGold = Math.max(maxGold, dfs(grid, i, j));
                }
            }
        }
        return maxGold;
    }

    private int dfs(int[][] grid, int r, int c) {
        int m = grid.length;
        int n = grid[0].length;

        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == 0) {
            return 0;
        }

        int currentGold = grid[r][c];
        grid[r][c] = 0; // Mark as visited for the current path

        int maxFromNeighbors = 0;
        // Explore neighbors: up, down, left, right
        maxFromNeighbors = Math.max(maxFromNeighbors, dfs(grid, r - 1, c));
        maxFromNeighbors = Math.max(maxFromNeighbors, dfs(grid, r + 1, c));
        maxFromNeighbors = Math.max(maxFromNeighbors, dfs(grid, r, c - 1));
        maxFromNeighbors = Math.max(maxFromNeighbors, dfs(grid, r, c + 1));

        grid[r][c] = currentGold; // Backtrack

        return currentGold + maxFromNeighbors;
    }
}
```
### Algorithm
*   Initialize `maxGold` to 0.
*   Iterate through each cell `(i, j)` of the grid.
*   If `grid[i][j] > 0`, start a DFS from this cell.
*   The DFS function takes the current cell `(r, c)`:
    *   Base Case: If `(r, c)` is out of bounds or has 0 gold, return 0.
    *   Collect gold from `(r, c)` and mark it as visited (e.g., `grid[r][c] = 0`).
    *   Recursively call DFS for all four neighbors and find the maximum gold `maxFromNeighbors` returned from these calls.
    *   Backtrack: Restore the original gold value of `grid[r][c]`.
    *   Return `currentGold + maxFromNeighbors`.
*   Update `maxGold` with the result of each initial DFS call.
*   Return `maxGold`.

# Solutions
### Java

```java
class Solution {
private
  final int[] dirs = {-1, 0, 1, 0, -1};
private
  int[][] grid;
private
  int m;
private
  int n;
public
  int getMaximumGold(int[][] grid) {
    m = grid.length;
    n = grid[0].length;
    this.grid = grid;
    int ans = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        ans = Math.max(ans, dfs(i, j));
      }
    }
    return ans;
  }
private
  int dfs(int i, int j) {
    if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0) {
      return 0;
    }
    int v = grid[i][j];
    grid[i][j] = 0;
    int ans = 0;
    for (int k = 0; k < 4; ++k) {
      ans = Math.max(ans, v + dfs(i + dirs[k], j + dirs[k + 1]));
    }
    grid[i][j] = v;
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number[][]} grid * @return {number} */ var getMaximumGold =
  function (grid) {
    const m = grid.length;
    const n = grid[0].length;
    const dfs = (i, j) => {
      if (i < 0 || i >= m || j < 0 || j >= n || !grid[i][j]) {
        return 0;
      }
      const v = grid[i][j];
      grid[i][j] = 0;
      let ans =
        v +
        Math.max(dfs(i - 1, j), dfs(i + 1, j), dfs(i, j - 1), dfs(i, j + 1));
      grid[i][j] = v;
      return ans;
    };
    let ans = 0;
    for (let i = 0; i < m; i++) {
      for (let j = 0; j < n; j++) {
        ans = Math.max(ans, dfs(i, j));
      }
    }
    return ans;
  };

```

### CPP

```cpp
class Solution {
public:
  int getMaximumGold(vector<vector<int>> &grid) {
    int m = grid.size(), n = grid[0].size();
    function<int(int, int)> dfs = [&](int i, int j) {
      if (i < 0 || i >= m || j < 0 || j >= n || !grid[i][j]) {
        return 0;
      }
      int v = grid[i][j];
      grid[i][j] = 0;
      int ans =
          v + max({dfs(i - 1, j), dfs(i + 1, j), dfs(i, j - 1), dfs(i, j + 1)});
      grid[i][j] = v;
      return ans;
    };
    int ans = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        ans = max(ans, dfs(i, j));
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def getMaximumGold(self, grid: List[List[int]]) -> int: def dfs(i: int, j: int) -> int: if not (0 <= i < m and 0 <= j < n and grid[i][j]): return 0 v = grid[i][j] grid[i][j] = 0 ans = max(dfs(i + a, j + b) for a, b in pairwise(dirs)) + v grid[i][j] = v return ans m, n = len(grid), len(grid[0]) dirs = (- 1, 0, 1, 0, - 1) return max(dfs(i, j) for i in range(m) for j in range(n))

```