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#.