Input: grid =[[0,6,0],[5,8,7],[0,9,0]]Output: 24Explanation:
[[0,6,0],[5,8,7],[0,9,0]]Path to get the maximum gold,9->8->7.
Example 2:
1
2
3
4
5
6
7
8
9
Input: grid =[[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]Output: 28Explanation:
[[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]Path to get the maximum gold,1->2->3->4->5->6->7.
One might think that this problem can be solved using DP similar to Leetcode 329 - Longest Increasing Path in a Matrix. Indeed, at face value, it seems we can use a 2D array to store at each position what’s the maximum path, which can give us a O(M*N) runtime.
However, unlike problem 329, here we cannot devise the caching strategy. We cannot store any meaningful solution for the overlapping subproblems. Lets look at example why.
Since 329 is looking for increasing path, same path cannot be used both directions.
1
2
3
0 6 0
5 8 7
0 9 0
Take the above matrix as an example. At position of element 7, if we are looking for longest increasing path, it’s 7,8. So at 8 the longest increasing path is not 8, 7. However, if we are finding the maximum sum, the result can come from any direction.
For this problem, for eg., say we started a DFS path from element grid[0][1] (element 6). The max path would be 6 -> 8 -> 9 as explained above. At element 8, (grid[1][1], we would have stored that the max path sum from grid[1][1] would be 8 -> 9, totalling 17.
But now say later in the nested for loop traversal of the grid, we start a DFS path from grid[2][1], (element 9). We can’t just use the memoized solution that we stored for grid[1][1] at 8, because it would mean we would revisit 9 which is not allowed. The max path sum at any element is effected by the path of visited elements we have already seen. Thus, there is no real meaningful method/reason to capture this information and use DP.
The best path can start at any nonzero cell and depends on which cells have already been visited, so we must explore all paths starting from every gold cell.
#include<vector>#include<algorithm>usingnamespace std;
classSolution {
public:int getMaximumGold(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
int maxGold =0;
for (int i =0; i < m; ++i) {
for (int j =0; j < n; ++j) {
maxGold = max(maxGold, helper(grid, i, j));
}
}
return maxGold;
}
private:constint DIR[4][2] = {{0,-1},{0,1},{-1,0},{1,0}};
inthelper(vector<vector<int>>& grid, int r, int c) {
if (r <0|| r >= (int)grid.size() || c <0|| c >= (int)grid[0].size() || grid[r][c] ==0) return0;
int gold = grid[r][c];
grid[r][c] =0; // mark visited
int maxGold =0;
for (int k =0; k <4; ++k) {
int nr = r + DIR[k][0];
int nc = c + DIR[k][1];
maxGold = max(maxGold, helper(grid, nr, nc));
}
grid[r][c] = gold; // restore
return gold + maxGold;
}
};
classSolution {
// left, right, up, downprivatestaticint[][] DIR =newint[][] { {0, -1}, {0, 1}, {-1, 0}, {1, 0}};
publicintgetMaximumGold(int[][] grid) {
int m = grid.length, n = grid[0].length;
int maxGold = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
maxGold = Math.max(maxGold, helper(grid, i, j));
}
}
return maxGold;
}
privateinthelper(int[][] grid, int r, int c) {
if (r < 0 || r == grid.length|| c < 0 || c == grid[0].length|| grid[r][c]== 0) {
return 0;
}
int gold = grid[r][c];
grid[r][c]= 0; // mark mine as visited by destroying itint maxGold = 0;
for (int i = 0; i < DIR.length; i++) {
int newR = r + DIR[i][0];
int newC = c + DIR[i][1];
maxGold = Math.max(maxGold, helper(grid, newR, newC));
}
grid[r][c]= gold; // fix the gold minereturn gold + maxGold;
}
}
classSolution:
defgetMaximumGold(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
max_gold =0defhelper(r: int, c: int) -> int:
if r <0or r >= m or c <0or c >= n or grid[r][c] ==0:
return0 gold = grid[r][c]
grid[r][c] =0 best =0for dr, dc in ((0,-1),(0,1),(-1,0),(1,0)):
best = max(best, helper(r+dr, c+dc))
grid[r][c] = gold
return gold + best
for i in range(m):
for j in range(n):
max_gold = max(max_gold, helper(i, j))
return max_gold
⏰ Time complexity: O(k*4^k), where k <= 25 is the number of cells that have gold. At each point, we can go to 4 neighbours - so, we can split into 4 paths, and that takes O(4^k). We have to do this for at most k times (not m*n times, as we will start DFS only when grid[r][c] has a gold mine, aka non-zero value). Hence O(k*4^k).
🧺 Space complexity: O(1) as we temporarily modify grid in place.
For each cell with non-zero gold, start a DFS with an empty visited set.
In DFS, return 0 if out-of-bounds, the cell is 0, or already visited; otherwise add the cell to visited, explore 4 neighbours, take the maximum, then remove from visited (backtrack) and return the accumulated sum.
Track the global maximum across all starts and return it.
#include<vector>#include<unordered_set>#include<string>#include<algorithm>usingnamespace std;
classSolution {
public:int getMaximumGold(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int maxGold =0;
for (int i =0; i < m; ++i) {
for (int j =0; j < n; ++j) {
unordered_set<int> visited;
maxGold = max(maxGold, helper(grid, i, j, visited));
}
}
return maxGold;
}
private:constint DIR[4][2] = {{0,-1},{0,1},{-1,0},{1,0}};
intkey(int r, int c, int cols) { return r * cols + c; }
inthelper(const vector<vector<int>>& gridConst, int r, int c, unordered_set<int>& visited) {
int m = gridConst.size(), n = gridConst[0].size();
if (r <0|| r >= m || c <0|| c >= n || gridConst[r][c] ==0) return0;
int k = key(r, c, n);
if (visited.count(k)) return0;
visited.insert(k);
int maxGold =0;
for (int i =0; i <4; ++i) {
int nr = r + DIR[i][0];
int nc = c + DIR[i][1];
maxGold = max(maxGold, helper(gridConst, nr, nc, visited));
}
visited.erase(k);
return gridConst[r][c] + maxGold;
}
};
from typing import List, Set, Tuple
classSolution:
defgetMaximumGold(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
max_gold =0defhelper(r: int, c: int, visited: Set[Tuple[int,int]]) -> int:
if r <0or r >= m or c <0or c >= n or grid[r][c] ==0or (r,c) in visited:
return0 visited.add((r,c))
best =0for dr, dc in ((0,-1),(0,1),(-1,0),(1,0)):
best = max(best, helper(r+dr, c+dc, visited))
visited.remove((r,c))
return grid[r][c] + best
for i in range(m):
for j in range(n):
max_gold = max(max_gold, helper(i, j, set()))
return max_gold