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.
This approach utilizes backtracking and depth-first search (DFS) to explore all possible paths to collect the maximum gold. Start from each cell containing gold and perform DFS to explore in all four possible directions (up, down, left, right). During the search, keep track of the total gold collected. Use backtracking to unvisit a cell after exploring all potential paths from it.
The C language implementation uses a recursive function 'dfs' to explore each valid path starting from a gold cell. It employs a grid to mark visited cells by setting their gold value to zero and restores them after backtracking is complete. This way, all potential paths can be explored to determine the path with the maximum gold.
Time complexity: O((m*n)^2) - In the worst-case scenario, each cell containing gold gets visited and backtracked.
Space complexity: O(m*n) - This results from recursive stack space and the grid modifications.
This approach involves using dynamic programming with bit masking to track visited states and optimize the path of maximum gold collection. It systematically calculates the maximum gold that can be gathered by starting from each gold cell and considering valid moves while ensuring no cell is revisited.
This implementation uses a bitmask to track visited states and dynamic programming to store interim computations. It only traverses unvisited gold-bearing cells and optimizes path selection for maximal gold collection efficiency. State visits are held in a DP table indexed by the bitmask, with recursive exploration to uncover superior paths.
Time complexity: O(2^(m*n) * m * n) given bitmask state examination.
Space complexity: O(2^(m*n) * m * n) due to DP storage needs for various path states.
We can enumerate each cell as the starting point, and then start a depth-first search from the starting point. During the search process, whenever we encounter a non-zero cell, we turn it into zero and continue the search. When we can no longer continue the search, we calculate the total amount of gold in the current path, then turn the current cell back into a non-zero cell, thus performing backtracking.
The time complexity is O(m times n times 3^k), where k is the maximum length of each path. Since each cell can only be visited once at most, the time complexity will not exceed O(m times n times 3^k). The space complexity is O(m times n).
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Backtracking with Depth-First Search | Time complexity: O((m*n)^2) - In the worst-case scenario, each cell containing gold gets visited and backtracked. Space complexity: O(m*n) - This results from recursive stack space and the grid modifications. |
| Dynamic Programming with Masking | Time complexity: O(2^(m*n) * m * n) given bitmask state examination. Space complexity: O(2^(m*n) * m * n) due to DP storage needs for various path states. |
| DFS | — |
| 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 |
Google Coding Interview Question - Path With Maximum Gold (LeetCode) • AlgosWithMichael • 39,361 views views
Watch 9 more video solutions →Practice Path with Maximum Gold with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor