Maximum Gold Collectible Along a Non-Revisiting Path
Solve this ProblemTest Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ grid.length, grid[0].length ≤ 6 - ◆
0 ≤ grid[i][j] ≤ 50; a cell holding 0 has no gold and can never be stepped on - ◆
A path may start at any cell, move to any horizontally or vertically adjacent cell, and never revisit a cell already on the current path
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Track the Path as a List, Scan It on Every Step
BruteTrack which cells are already part of the current path as a growing list of coordinates. Before stepping onto a new cell, walk the entire list checking whether that coordinate already appears in it. This correctly prevents revisiting, but the list grows with every step deeper into a path, so this check gets more expensive the longer the path already is — the very last step of a long path re-examines every single cell visited before it, one at a time.
O(3^(cells) · cells)O(cells²)1class Solution {
2 public int maxGoldCollected(int[][] grid) {
3 int n = grid.length, m = grid[0].length;
4 int best = 0;
5 for (int r = 0; r < n; r++) {
6 for (int c = 0; c < m; c++) {
7 List<int[]> path = new ArrayList<>();
8 best = Math.max(best, dfs(grid, r, c, path));
9 }
10 }
11 return best;
12 }
13
14 private int dfs(int[][] grid, int r, int c, List<int[]> path) {
15 int n = grid.length, m = grid[0].length;
16 if (r < 0 || r >= n || c < 0 || c >= m || grid[r][c] == 0) return 0;
17 for (int[] p : path) {
18 if (p[0] == r && p[1] == c) return 0;
19 }
20 path.add(new int[]{r, c});
21 int val = grid[r][c];
22 int down = dfs(grid, r + 1, c, path);
23 int up = dfs(grid, r - 1, c, path);
24 int right = dfs(grid, r, c + 1, path);
25 int left = dfs(grid, r, c - 1, path);
26 path.remove(path.size() - 1);
27 return val + Math.max(Math.max(down, up), Math.max(right, left));
28 }
29}Optimal — Track Visited Cells With a Direct-Lookup Grid
OptimalUse a boolean grid, one flag per cell, instead of a growing list. Checking whether a cell is on the current path becomes a single direct lookup — no matter how long the path already is. Stepping onto a cell flips its flag to true, and backtracking off it flips it back to false, both O(1). The set of paths explored is exactly the same as the brute-force version; only the cost of the "is this cell already in my path" question changes, from scaling with path length to being constant.
O(3^(cells))O(cells)1class Solution {
2 public int maxGoldCollected(int[][] grid) {
3 int n = grid.length, m = grid[0].length;
4 boolean[][] visited = new boolean[n][m];
5 int best = 0;
6 for (int r = 0; r < n; r++) {
7 for (int c = 0; c < m; c++) {
8 best = Math.max(best, dfs(grid, r, c, visited));
9 }
10 }
11 return best;
12 }
13
14 private int dfs(int[][] grid, int r, int c, boolean[][] visited) {
15 int n = grid.length, m = grid[0].length;
16 if (r < 0 || r >= n || c < 0 || c >= m || visited[r][c] || grid[r][c] == 0) return 0;
17 visited[r][c] = true;
18 int val = grid[r][c];
19 int down = dfs(grid, r + 1, c, visited);
20 int up = dfs(grid, r - 1, c, visited);
21 int right = dfs(grid, r, c + 1, visited);
22 int left = dfs(grid, r, c - 1, visited);
23 visited[r][c] = false;
24 return val + Math.max(Math.max(down, up), Math.max(right, left));
25 }
26}