Leetcode 1219. Path with Maximum Gold
Problem Explanation
The problem involves finding the maximum amount of gold you can collect starting from any cell in a grid (2D matrix) of size m x n
where each cell contains a certain amount of gold. You can only move one step to the left, right, up, or down at any time, and you can't visit the same cell more than once nor visit a cell with 0 gold. The challenge is to carefully devise a path that gives the maximum amount of gold.
Let's walk through an example:
Given the following grid:
1 2 3[ 4 [0, 6, 0], 5 [5, 8, 7], 6 [0, 9, 0] 7]
One possible optimal path would be starting from the cell with 9
gold (2nd row, 2nd column), then moving to the cell above it with 8
gold, and finally to the right cell with 7
gold. This gives a total of 24
gold, which is the maximum you can collect from the grid.
Approach
The solution uses a Depth-First Search (DFS) approach starting from each cell in the grid that has some gold. DFS is a useful algorithm for traversing through all nodes of a graph (or cells of a grid), particularly when thereโs a need to travel through nodes deeply before exploring neighbors.
When we start the DFS from a particular cell, we mark it as visited by setting it to 0
gold. Then we try moving in each direction (left, right, up and down). For each valid movement, we again perform the DFS from the next cell and finally take the maximum of all values returned from these DFS calls. Our DFS call will return 0
when we either go out of the bounds of the grid or the cell is already visited (i.e., has 0
gold). We then unmark the current cell (set the gold back) to allow other DFS traversals to collect from it.
Python Solution
1 2python 3class Solution: 4 def getMaximumGold(self, grid: List[List[int]]) -> int: 5 def dfs(i: int, j: int) -> int: 6 # Boundary case and cell is visited case 7 if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == 0: 8 return 0 9 gold = grid[i][j] 10 # Mark cell as visited 11 grid[i][j] = 0 12 max_gold = max(dfs(i+1, j), dfs(i-1, j), dfs(i, j+1), dfs(i, j-1)) 13 # Unmark cell to allow subsequent DFS to collect gold 14 grid[i][j] = gold 15 return gold + max_gold 16 17 return max(dfs(i, j) for i in range(len(grid)) for j in range(len(grid[0])))
The getMaximumGold
function uses the helper function dfs
to explore the grid deeply in every valid direction and takes the maximum of the total gold collected from each DFS traversal.
Java Solution
1
2java
3class Solution {
4 public int getMaximumGold(int[][] grid) {
5 int max = 0;
6 for(int i=0; i<grid.length; i++) {
7 for(int j=0; j<grid[0].length; j++) {
8 max = Math.max(max, dfs(grid, i, j));
9 }
10 }
11 return max;
12 }
13
14 private int dfs(int[][] grid, int i, int j) {
15 if(i<0 || j<0 || i == grid.length || j == grid[0].length || grid[i][j]==0)
16 return 0;
17 int gold = grid[i][j];
18 grid[i][j] = 0;
19 int maxGold = 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)));
20 grid[i][j] = gold;
21 return gold + maxGold;
22 }
23}
The Java implementation is similar to the Python implementation. The for
loops in getMaximumGold
initiate the DFS traversal from every cell in the grid, and the dfs
function completes the depth-first search.
JavaScript Solution
1
2javascript
3class Solution {
4 dfs(grid, i, j) {
5 if (!this.isInBounds(grid, i, j) || grid[i][j] === 0){
6 return 0;
7 }
8 let goldCount = grid[i][j];
9 grid[i][j] = 0;
10 const maxGold = Math.max(this.dfs(grid, i + 1, j), this.dfs(grid, i - 1, j), this.dfs(grid, i, j + 1), this.dfs(grid, i, j - 1));
11 grid[i][j] = goldCount;
12 return goldCount + maxGold;
13 }
14
15 isInBounds(grid, i, j) {
16 return i >= 0 && i < grid.length && j >= 0 && j < grid[0].length;
17 }
18
19 getMaximumGold(grid) {
20 let max = 0;
21 for(let i = 0; i < grid.length; i++){
22 for(let j = 0; j < grid[0].length; j++){
23 max = Math.max(max, this.dfs(grid, i, j));
24 }
25 }
26 return max;
27 }
28}
The isInBounds
function is an additional helper function used to check if a particular cell is within the grid boundaries.
C++ Solution
1 2cpp 3class Solution { 4public: 5 int maxGold = 0, n, m; 6 7 bool isSafe(vector <vector<int>>& grid, int i, int j){ 8 // Checking array bounds and cell is non-zero 9 return (i >= 0 && j >= 0 && i < grid.size() && j < grid[0].size() && grid[i][j]); 10 } 11 12 void dfs(vector <vector<int>>& grid, int i, int j, int currentGold){ 13 // Updating maximum gold 14 if(currentGold > this->maxGold) 15 this->maxGold = currentGold; 16 17 // Check up, down, left, right 18 int dx[] = {0, 0, -1, 1}; 19 int dy[] = {-1, 1, 0, 0}; 20 21 for (int idx = 0; idx < 4; idx++){ 22 int x = i + dx[idx], y = j + dy[idx]; 23 if(isSafe(grid, x, y)){ 24 int temp = grid[x][y]; 25 // Mark the cell as visited 26 grid[x][y] = 0; 27 dfs(grid, x, y, currentGold + temp); 28 // Mark the cell as unvisited for other DFS calls 29 grid[x][y] = temp; 30 } 31 } 32 } 33 34 int getMaximumGold(vector<vector<int>>& grid) { 35 n = grid.size(); 36 m = grid[0].size(); 37 for(int i = 0; i < n; i++){ 38 for(int j = 0; j < m; j++){ 39 if(grid[i][j]){ 40 // Every cell with non-zero gold is a potential starting point 41 dfs(grid, i, j, grid[i][j]); 42 } 43 } 44 } 45 return this->maxGold; 46 } 47};
In the C++ implementation, we use two additional arrays, dx[] and dy[]
to help with the movement in four directions (up, down, left, right).
C# Solution
1 2csharp 3public class Solution { 4 private int[][] directions = new int[][]{{-1,0},{1,0},{0,-1},{0,1}}; 5 private int rows, cols; 6 7 public int GetMaximumGold(int[][] grid) { 8 if (grid == null || grid.Length == 0 || grid[0].Length == 0) 9 return 0; 10 11 rows = grid.Length; 12 cols = grid[0].Length; 13 int maxGold = 0; 14 15 for(int row=0; row<rows; row++){ 16 for(int col=0; col<cols; col++){ 17 if(grid[row][col] != 0){ 18 maxGold = Math.Max(maxGold, dfs(grid, row, col)); 19 } 20 } 21 } 22 23 return maxGold; 24 } 25 26 private int dfs(int[][] grid, int row, int col){ 27 if(row < 0 || col < 0 || row == rows || col == cols || grid[row][col] == 0) 28 return 0; 29 30 int original = grid[row][col]; 31 grid[row][col] = 0; 32 int maxPath = 0; 33 foreach(var dir in directions){ 34 int x = row + dir[0]; 35 int y = col + dir[1]; 36 maxPath = Math.Max(maxPath, dfs(grid, x, y)); 37 } 38 grid[row][col] = original; 39 40 return maxPath + original; 41 } 42}
The C# implementation is quite similar to all the other language solutions, the grid is scanned for non-zero cells and each is used as a potential starting point for the DFS to find the maximum possible gold that can be collected.# Summary
The problem is solved using a Depth-First Search (DFS) approach. The DFS starts at each cell that contains gold, and subsequent DFS calls are made for every valid move from the current cell. If a cell is visited while performing DFS, it is marked to avoid repeated visits, but subsequently unmarked to allow other DFS traversals to collect gold from it. This kind of marking & unmarking cells in a reversible manner makes this problem a classic example of backtracking that can be seen in several other problems.
The time complexity of the solution is O(4^(m*n))
because in the worst case, the DFS will go in all 4 directions from each cell. The space complexity is O(m*n)
due to the recursion stack used by the DFS.
There isn't an apparent way to optimize this further because all cells with gold have to be visited and all possible moves made to find the maximum gold. The approach will be the same in all languages - Python, Java, JavaScript, C++, and C#.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.