Path with Maximum Gold
Medium · Backtracking · Explanation and code example
Backtracking (BFS)
How it works
We can also solve this problem using BFS with bitmask state tracking. Each cell containing gold is assigned a unique index, and we use a bitmask to track which cells have been visited along the current path. This allows us to explore all possible paths level by level while ensuring we do not revisit any cell within the same path.
Steps
- Assign a unique index to each cell containing gold.
- For each gold cell, start a BFS with the initial state containing the cell's position, the gold collected so far, and a bitmask marking this cell as visited.
- For each state in the queue, update the maximum gold collected.
- Explore all four neighbors. If a neighbor contains gold and has not been visited in the current path (check the bitmask), add a new state to the queue with updated gold and an updated
bitmask. - Continue until the queue is empty and return the maximum gold found.
Complexity
- Time complexity:
O(N * 3 ^ N) - Space complexity:
O(N)
Where
Nis the number of cells which contain gold.
Things to watch for
Forgetting to Backtrack
The most common mistake is forgetting to restore the cell's state after exploring a path. Whether using a visited set or modifying the grid directly, failing to backtrack means other paths starting from different cells cannot use that position. Always remove the cell from the visited set or restore its original value before returning.
Starting Only from Corner Cells
Some solutions incorrectly assume the optimal path must start from a corner or edge. The problem allows starting from any cell containing gold, so you must try all possible starting positions. Missing interior starting cells can lead to suboptimal results.
Not Handling Zero Cells Correctly
Cells with value zero cannot be visited, but some solutions forget to check for zeros when determining valid neighbors. Additionally, when using the grid modification approach to mark cells as visited (setting them to zero), ensure you save the original value before modification so it can be properly restored during backtracking.
Python code example
from collections import deque
class Solution:
def getMaximumGold(self, grid: list[list[int]]) -> int:
ROWS, COLS = len(grid), len(grid[0])
directions = [1, 0, -1, 0, 1]
index = [[0] * COLS for _ in range(ROWS)]
idx = 0
for r in range(ROWS):
for c in range(COLS):
if grid[r][c] != 0:
index[r][c] = idx
idx += 1
res = 0
for r in range(ROWS):
for c in range(COLS):
if grid[r][c] > 0:
q = deque([(r, c, grid[r][c], 1 << index[r][c])])
while q:
row, col, gold, mask = q.popleft()
res = max(res, gold)
for i in range(4):
nr, nc = row + directions[i], col + directions[i + 1]
if 0 <= nr < ROWS and 0 <= nc < COLS and grid[nr][nc] > 0:
idx = index[nr][nc]
if not (mask & (1 << idx)):
q.append((nr, nc, gold + grid[nr][nc], mask | (1 << idx)))
return res
C++ code example
class Solution {
public:
int getMaximumGold(vector<vector<int>>& grid) {
int ROWS = grid.size(), COLS = grid[0].size();
vector<vector<int>> index(ROWS, vector<int>(COLS, 0));
int idx = 0;
int directions[] = {1, 0, -1, 0, 1};
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
if (grid[r][c] != 0) {
index[r][c] = idx++;
}
}
}
int res = 0;
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
if (grid[r][c] > 0) {
queue<tuple<int, int, int, int>> q;
q.push({r, c, grid[r][c], 1 << index[r][c]});
while (!q.empty()) {
auto [row, col, gold, mask] = q.front();q.pop();
res = max(res, gold);
for (int i = 0; i < 4; i++) {
int nr = row + directions[i], nc = col + directions[i + 1];
if (nr >= 0 && nr < ROWS && nc >= 0 && nc < COLS && grid[nr][nc] > 0) {
int newIdx = index[nr][nc];
if ((mask & (1 << newIdx)) == 0) {
q.push({nr, nc, gold + grid[nr][nc], mask | (1 << newIdx)});
}
}
}
}
}
}
}
return res;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.