Watch 10 video solutions for Path with Maximum Gold, a medium level problem involving Array, Backtracking, Matrix. This walkthrough by AlgosWithMichael has 39,361 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
0 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.lengthn == grid[i].length1 <= m, n <= 150 <= grid[i][j] <= 100Problem Overview: You are given an m x n grid where each cell contains some amount of gold. You can start from any cell with gold, move up/down/left/right, and cannot visit the same cell twice. The goal is to collect the maximum total gold along a valid path.
Approach 1: Backtracking with Depth-First Search (Exponential Time)
This problem naturally maps to graph traversal on a grid. Treat each gold cell as a node and explore all possible paths using DFS. Start a search from every cell with gold, recursively move in four directions, and temporarily mark the cell as visited (often by setting it to 0). After exploring a path, restore the value to allow other paths to use the cell. This classic backtracking pattern ensures every valid path is considered while preventing revisits. The time complexity is roughly O((m*n) * 4^k), where k is the number of gold cells, and space complexity is O(k) for the recursion stack. In practice, constraints are small enough that this performs well.
Approach 2: Dynamic Programming with Bitmasking
If the number of gold cells is small, you can model the problem as a state search using bitmasks. First compress the grid into a list of gold cells, then represent visited cells using a bitmask. The DP state becomes dp[mask][i], meaning the maximum gold collected when the visited set is mask and the current position is cell i. Transitions occur by moving to adjacent gold cells whose bits are not yet set. This approach converts the traversal into a graph DP similar to traveling path problems. The time complexity is about O(k * 2^k * 4) and space complexity is O(k * 2^k). It avoids repeated exploration but uses more memory.
Both approaches rely heavily on grid traversal patterns from matrix problems and adjacency checks on a 2D array. The key observation is that paths cannot revisit cells, which makes the search space manageable.
Recommended for interviews: Backtracking with DFS is the expected solution. Interviewers want to see that you can model the grid as a graph, mark cells as visited during recursion, and correctly restore state after exploring a branch. The DP with bitmasking approach demonstrates deeper optimization thinking but is rarely required unless constraints are much larger.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with DFS | O((m*n) * 4^k) | O(k) | Best general solution for interview constraints and typical grid sizes |
| Dynamic Programming with Bitmask | O(k * 2^k * 4) | O(k * 2^k) | When number of gold cells is small and repeated path exploration should be avoided |