Path with Maximum Gold
Medium · Backtracking · Array · Backtracking · Matrix · Depth-First Search
Problem
A gold mine is an m x n grid where each cell holds some amount of gold, and 0 means the cell is empty. Collect as much gold as you can under these rules:
- whenever you stand in a cell, you collect all of its gold;
- from a cell you may step up, down, left or right;
- you may not visit the same cell twice, and you may never enter a cell with 0 gold;
- you may start and stop at any cell that holds gold.
Return the most gold a single walk can collect.
Examples
Input: grid = [[4,0,2],[3,1,5]] Output: 15
The walk 4 → 3 → 1 → 5 → 2 visits every gold cell.
Input: grid = [[8,0],[0,1]] Output: 8
The two gold cells only touch diagonally, so the best is the 8 alone.
Input: grid = [[0,6,0],[5,8,7],[0,9,0]] Output: 24
Through the center a walk can use only two arms: 9 → 8 → 7 collects 24.
Constraints
- m == grid.length, n == grid[i].length
- 1 <= m, n <= 15
- 0 <= grid[i][j] <= 100
- at most 25 cells contain gold
Approaches
- Baseline: enumerate paths with a copied visited set — time O(k² · 3^k), space O(k²)
Follow-up
The search is exponential in the number of gold cells, which the limit of 25 keeps small. The use cases maximize the number of cells instead of the gold and fix the starting cell.
Related problems
Start free on Cariara · Coding problems · System design studio
