Path with Maximum Gold

Med

#1138Time: 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).1 company

Patterns

Backtracking

Data structures

Array Matrix

Companies

Geico

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

The brute-force algorithm proceeds as follows:

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.
Generate Permutations: Generate all possible orderings (permutations) of these k cells. There are k! such permutations.
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.
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.

Complexity

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

Trade-offs

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.

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.

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.

Walkthrough

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:

Initialize a global variable maxGold = 0.
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.
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).
Update maxGold = Math.max(maxGold, result_of_dfs).
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.

1class Solution {2    public int getMaximumGold(int[][] grid) {3        int maxGold = 0;4        int m = grid.length;5        int n = grid[0].length;6 7        for (int i = 0; i < m; i++) {8            for (int j = 0; j < n; j++) {9                if (grid[i][j] > 0) {10                    maxGold = Math.max(maxGold, dfs(grid, i, j));11                }12            }13        }14        return maxGold;15    }16 17    private int dfs(int[][] grid, int r, int c) {18        int m = grid.length;19        int n = grid[0].length;20 21        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == 0) {22            return 0;23        }24 25        int currentGold = grid[r][c];26        grid[r][c] = 0; // Mark as visited for the current path27 28        int maxFromNeighbors = 0;29        // Explore neighbors: up, down, left, right30        maxFromNeighbors = Math.max(maxFromNeighbors, dfs(grid, r - 1, c));31        maxFromNeighbors = Math.max(maxFromNeighbors, dfs(grid, r + 1, c));32        maxFromNeighbors = Math.max(maxFromNeighbors, dfs(grid, r, c - 1));33        maxFromNeighbors = Math.max(maxFromNeighbors, dfs(grid, r, c + 1));34 35        grid[r][c] = currentGold; // Backtrack36 37        return currentGold + maxFromNeighbors;38    }39}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2private3  final int[] dirs = {-1, 0, 1, 0, -1};4private5  int[][] grid;6private7  int m;8private9  int n;10public11  int getMaximumGold(int[][] grid) {12    m = grid.length;13    n = grid[0].length;14    this.grid = grid;15    int ans = 0;16    for (int i = 0; i < m; ++i) {17      for (int j = 0; j < n; ++j) {18        ans = Math.max(ans, dfs(i, j));19      }20    }21    return ans;22  }23private24  int dfs(int i, int j) {25    if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0) {26      return 0;27    }28    int v = grid[i][j];29    grid[i][j] = 0;30    int ans = 0;31    for (int k = 0; k < 4; ++k) {32      ans = Math.max(ans, v + dfs(i + dirs[k], j + dirs[k + 1]));33    }34    grid[i][j] = v;35    return ans;36  }37}

1/** * @param {number[][]} grid * @return {number} */ var getMaximumGold =2  function (grid) {3    const m = grid.length;4    const n = grid[0].length;5    const dfs = (i, j) => {6      if (i < 0 || i >= m || j < 0 || j >= n || !grid[i][j]) {7        return 0;8      }9      const v = grid[i][j];10      grid[i][j] = 0;11      let ans =12        v +13        Math.max(dfs(i - 1, j), dfs(i + 1, j), dfs(i, j - 1), dfs(i, j + 1));14      grid[i][j] = v;15      return ans;16    };17    let ans = 0;18    for (let i = 0; i < m; i++) {19      for (let j = 0; j < n; j++) {20        ans = Math.max(ans, dfs(i, j));21      }22    }23    return ans;24  };

1class Solution {2public:3  int getMaximumGold(vector<vector<int>> &grid) {4    int m = grid.size(), n = grid[0].size();5    function<int(int, int)> dfs = [&](int i, int j) {6      if (i < 0 || i >= m || j < 0 || j >= n || !grid[i][j]) {7        return 0;8      }9      int v = grid[i][j];10      grid[i][j] = 0;11      int ans =12          v + max({dfs(i - 1, j), dfs(i + 1, j), dfs(i, j - 1), dfs(i, j + 1)});13      grid[i][j] = v;14      return ans;15    };16    int ans = 0;17    for (int i = 0; i < m; ++i) {18      for (int j = 0; j < n; ++j) {19        ans = max(ans, dfs(i, j));20      }21    }22    return ans;23  }24};

1class Solution:2    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))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem