In this guide, you will get 1219. Path with Maximum Gold LeetCode Solution with the best time and space complexity. The solution to Path with Maximum Gold problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
In a gold mine grid of size m x n, each cell in this mine has an integer representing the amount of gold in that cell, 0 if it is empty.
Return the maximum amount of gold you can collect under the conditions:
Every time you are located in a cell you will collect all the gold in that cell.
From your position, you can walk one step to the left, right, up, or down.
You can’t visit the same cell more than once.
Never visit a cell with 0 gold.
You can start and stop collecting gold from any position in the grid that has some gold.
Example 1:
Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
Output: 24
Explanation:
[[0,6,0],
[5,8,7],
[0,9,0]]
Path to get the maximum gold, 9 -> 8 -> 7.
Example 2:
Input: grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
Output: 28
Explanation:
[[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.
m == grid.length
n == grid[i].length
1 <= m, n <= 15
0 <= grid[i][j] <= 100
There are at most 25 cells containing gold.
Complexity Analysis
Time Complexity: O(3^{mn})
Space Complexity: O(mn)
1219. Path with Maximum Gold LeetCode Solution in C++
class Solution {
public:
int getMaximumGold(vector<vector<int>>& grid) {
int ans = 0;
for (int i = 0; i < grid.size(); ++i)
for (int j = 0; j < grid[0].size(); ++j)
ans = max(ans, dfs(grid, i, j));
return ans;
}
private:
int dfs(vector<vector<int>>& grid, int i, int j) {
if (i < 0 || j < 0 || i == grid.size() || j == grid[0].size())
return 0;
if (grid[i][j] == 0)
return 0;
const int gold = grid[i][j];
grid[i][j] = 0; // Mark as visited.
const int maxPath = max({dfs(grid, i + 1, j), dfs(grid, i - 1, j),
dfs(grid, i, j + 1), dfs(grid, i, j - 1)});
grid[i][j] = gold;
return gold + maxPath;
}
}; /* code provided by PROGIEZ */
1219. Path with Maximum Gold LeetCode Solution in Java
class Solution {
public int getMaximumGold(int[][] grid) {
int ans = 0;
for (int i = 0; i < grid.length; ++i)
for (int j = 0; j < grid[0].length; ++j)
ans = Math.max(ans, dfs(grid, i, j));
return ans;
}
private int dfs(int[][] grid, int i, int j) {
if (i < 0 || j < 0 || i == grid.length || j == grid[0].length)
return 0;
if (grid[i][j] == 0)
return 0;
final int gold = grid[i][j];
grid[i][j] = 0; // Mark as visited.
final int maxPath = Math.max(Math.max(dfs(grid, i + 1, j), dfs(grid, i - 1, j)),
Math.max(dfs(grid, i, j + 1), dfs(grid, i, j - 1)));
grid[i][j] = gold;
return gold + maxPath;
}
} // code provided by PROGIEZ
1219. Path with Maximum Gold LeetCode Solution in Python
class Solution:
def getMaximumGold(self, grid: list[list[int]]) -> int:
def dfs(i: int, j: int) -> int:
if i < 0 or j < 0 or i == len(grid) or j == len(grid[0]):
return 0
if grid[i][j] == 0:
return 0
gold = grid[i][j]
grid[i][j] = 0 # Mark as visited.
maxPath = max(dfs(i + 1, j), dfs(i - 1, j),
dfs(i, j + 1), dfs(i, j - 1))
grid[i][j] = gold
return gold + maxPath
return max(dfs(i, j)
for i in range(len(grid))
for j in range(len(grid[0]))) # code by PROGIEZ
