Command Palette

Search for a command to run...

Hectal
Problem 42.5 · Pattern Recognition DrillsMedium

Path with Maximum Gold

What it teaches:

Practise it on judges as “Path with Maximum Gold”.

In plain words

You are in a gold mine and may walk between neighbouring cells that have gold, never entering the same cell twice. The mine is tiny, so just try it: start from every gold cell, try every direction, and when a walk gets stuck, step back and try the next direction. While you stand on a cell, mark it as empty so you can't come back to it, and put the gold back when you step away.

Return the most gold one walk can collect. Example: grid = [[0,6,0],[5,8,7],[0,9,0]] → 24.

The problem

Collect gold by walking up/down/left/right through cells with gold > 0, never visiting a cell twice, starting and stopping anywhere. Return the most gold you can collect.

Example 1

Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
Output: 24

9 → 8 → 7.

Constraints

  • 1 ≤ rows, cols ≤ 15
  • At most 25 cells contain gold

Pattern clues in the wording

  • → Simple paths (no revisits)
  • → Tiny limits
  • → Maximum over all paths

Stuck? Take one hint at a time

Solution · starter
class Solution {
    public int getMaximumGold(int[][] grid) {
        return 0;
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#InputExpected
1
grid = [[0,6,0],[5,8,7],[0,9,0]]
24
2
grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
28

From slow to fast

Approaches

1. Backtracking from every gold cell · O(cells × 3^gold)
1

Backtracking from every gold cell

Time O(cells × 3^gold) Space O(gold)

DFS returns the best gold from here; temporarily set the cell to 0 while exploring.

▶ Dry run: Try every walk, undo on the way backgrid = [[0,6,0],[5,8,7],[0,9,0]]
0
6
0
5
8
7
0
9
0

best(vars)

0

Step 1/5Every cell with gold can be a starting point. Try them in reading order.

Approach 1
class Solution {
    public int getMaximumGold(int[][] grid) {
        int best = 0;
        for (int r = 0; r < grid.length; r++)
            for (int c = 0; c < grid[0].length; c++)
                if (grid[r][c] > 0) best = Math.max(best, dfs(grid, r, c));
        return best;
    }

    private int dfs(int[][] g, int r, int c) {
        if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] == 0) return 0;
        int gold = g[r][c];
        g[r][c] = 0;
        int more = Math.max(Math.max(dfs(g, r + 1, c), dfs(g, r - 1, c)), Math.max(dfs(g, r, c + 1), dfs(g, r, c - 1)));
        g[r][c] = gold;
        return gold + more;
    }
}

Verdict: Fine because at most 25 cells hold gold.

Before you submit

Edge cases and common mistakes

Test these inputs

  • No gold (0)
  • One isolated cell

Mistakes people make

  • Trying DP over cells (the best continuation depends on which cells were already used).

Interview

Follow-up questions

What clue rules out DP here?