Solved! Leetcode 1219. Path with Maximum Gold

source: https://leetcode.com/problems/path-with-maximum-gold/description/

Description: Path with Maximum Gold

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

<strong>Input:</strong> grid = [[0,6,0],[5,8,7],[0,9,0]]
<strong>Output:</strong> 24
<strong>Explanation:</strong>
[[0,6,0],
 [5,8,7],
 [0,9,0]]
Path to get the maximum gold, 9 -> 8 -> 7.

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

<strong>Input:</strong> grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
<strong>Output:</strong> 28
<strong>Explanation:</strong>
[[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.

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.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 15
0 <= grid[i][j] <= 100
There are at most 25 cells containing gold.

Solution

class Solution {
    public int getMaximumGold(int[][] grid) {
        if(grid==null || grid.length==0){
            return -1;
        }
        // starting from each cell, calculate the path sum and return the maximum sum
        // for the given grid [[0,6,0],[5,8,7],[0,9,0]]
        // for cell(0,1), there are 3 valid paths
        // 1. 6 -> 8 -> 5 = 19
        // 2. 6 -> 8 -> 9 = 23
        // 3. 6 -> 8 -> 7 = 21
        // max = 23
        // we need to find the max path sum for each cell and return the max
        int m = grid.length;
        int n = grid[0].length;
        int max = 0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]!=0){
                    max = Math.max(max, dfs(grid, i, j, m, n));
                }
            }
        }
        return max;
    }

    private int dfs(int[][] grid, int r, int c, int m, int n){
        int[][] xy = {{-1, 0}, {1, 0}, {0, 1}, {0,-1}};
        int max = 0;

        for(int i=0;i<xy.length;i++){
            int newR = xy[i][0] + r;
            int newC = xy[i][1] + c;

            if(isValid(grid, newR, newC, m , n)){

                int temp = grid[r][c];
                grid[r][c]= 0;
                max = Math.max(max,  dfs(grid, newR, newC, m , n));
                //backtrack
                grid[r][c] = temp;
            }

        }

        return grid[r][c] +   max;
    }

    private boolean isValid(int[][] grid, int r, int c, int m , int n){
        return r >=0 && r < m 
            && c >=0 && c < n
            && grid[r][c]!=0;
    }
}

class Solution {

public int getMaximumGold(int[][] grid) {

if(grid==null || grid.length==0){

return -1;

}

// starting from each cell, calculate the path sum and return the maximum sum

// for the given grid [[0,6,0],[5,8,7],[0,9,0]]

// for cell(0,1), there are 3 valid paths

// 1. 6 -> 8 -> 5 = 19

// 2. 6 -> 8 -> 9 = 23

// 3. 6 -> 8 -> 7 = 21

// max = 23

// we need to find the max path sum for each cell and return the max

int m = grid.length;

int n = grid[0].length;

int max = 0;

for(int i=0;i<m;i++){

for(int j=0;j<n;j++){

if(grid[i][j]!=0){

max = Math.max(max, dfs(grid, i, j, m, n));

}

return max;

}

private int dfs(int[][] grid, int r, int c, int m, int n){

int[][] xy = {{-1, 0}, {1, 0}, {0, 1}, {0,-1}};

int max = 0;

for(int i=0;i<xy.length;i++){

int newR = xy[i][0] + r;

int newC = xy[i][1] + c;

if(isValid(grid, newR, newC, m , n)){

int temp = grid[r][c];

grid[r][c]= 0;

max = Math.max(max, dfs(grid, newR, newC, m , n));

//backtrack

grid[r][c] = temp;

}

return grid[r][c] + max;

}

private boolean isValid(int[][] grid, int r, int c, int m , int n){

return r >=0 && r < m

&& c >=0 && c < n

&& grid[r][c]!=0;

}

Time Complexity

M*N*3^G, We are only running recursion in 3 direction (except for the starting call), as previous cell is already visited and cannot be visited again, where G indicate gold cells

Space Complexity

O(G), G – Total golden cells in the grid.

As the DFS call can only go so far as to visit all connected Golden cells, it has O(G)O(G)O(G) space complexity.

Rate this post

Coddicted