Path with Maximum Gold

Path with Maximum Gold

What is this problem about?

The Path with Maximum Gold problem gives you a grid where cells contain gold amounts (0 means empty). Starting from any non-zero cell, you can move in 4 directions without revisiting cells in the same path. Find the maximum gold you can collect in a single path. This coding problem uses DFS backtracking from each starting cell. The array, matrix, and backtracking interview pattern is the core.

Why is this asked in interviews?

Goldman Sachs, Microsoft, Meta, Amazon, and Google ask this because it tests DFS with backtracking on a grid — the ability to explore all paths from each starting point while restoring the grid state. Unlike dynamic programming, the "no revisiting" constraint requires explicit backtracking.

Algorithmic pattern used

DFS with in-place backtracking. For each non-zero cell as a starting point: run DFS. At each step: save current value, set it to 0 (mark visited), explore 4 neighbors, accumulate max gold. Restore the value after returning (backtrack). Track the overall maximum.

Example explanation

Grid:

0  6  0
5  8  7
0  9  0

Start at 9 (row 2, col 1): DFS explores paths. Path 9→8→7: 24. Path 9→8→5: 22. Path 9→8→6: 23. Also start at 8: can go to 6,5,7,9. Path 8→9→... etc. Maximum = 24 (via 7→8→9 or similar optimal path).

Common mistakes candidates make

• Not restoring (backtracking) the grid after DFS — corrupts future explorations.
• Not starting from every possible non-zero cell.
• Visiting cells with value 0 (should only start and traverse non-zero cells).
• Using a separate visited array instead of in-place zero-marking.

Interview preparation tip

Grid backtracking problems always use the "set to 0, explore, restore" pattern for in-place visited marking. This avoids extra space and is clean to implement. Practice this on "word search," "knight's tour," and similar grid DFS problems. The maximum gold problem is a good introduction to backtracking on grids before tackling harder variants with constraints.