LeetCode 1219: Path with Maximum Gold Solution

Master LeetCode problem 1219 (Path with Maximum Gold), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1219. Path with Maximum Gold

Medium

Array Backtracking Matrix

Problem Explanation

Explanation:

To solve this problem, we can use a depth-first search (DFS) algorithm to explore all possible paths starting from each cell with gold. At each step, we can move in four directions (left, right, up, down) and collect the gold in the current cell. We need to keep track of visited cells and avoid revisiting them.

Initialize a variable maxGold to store the maximum gold collected.
Iterate through each cell in the grid:
- If the cell contains gold, start DFS from that cell.
In the DFS function:
- Update the maxGold if the current path's gold is greater.
- Explore the four directions, if valid, and recursively call the DFS function.
The DFS function should return the total gold collected in that path.
Return maxGold as the final result.

Time Complexity: The time complexity is O(mn4^(m*n)) where m and n are the dimensions of the grid.

Space Complexity: The space complexity is O(m*n) for the recursion stack and visited cells.

Solution Code

class Solution {
    public int getMaximumGold(int[][] grid) {
        int maxGold = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] > 0) {
                    maxGold = Math.max(maxGold, dfs(grid, i, j));
                }
            }
        }
        return maxGold;
    }
    
    private int dfs(int[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0) {
            return 0;
        }
        
        int gold = grid[i][j];
        grid[i][j] = 0; // mark as visited
        
        int maxGold = 0;
        maxGold = Math.max(maxGold, gold + dfs(grid, i + 1, j));
        maxGold = Math.max(maxGold, gold + dfs(grid, i - 1, j));
        maxGold = Math.max(maxGold, gold + dfs(grid, i, j + 1));
        maxGold = Math.max(maxGold, gold + dfs(grid, i, j - 1));
        
        grid[i][j] = gold; // revert back
        
        return maxGold;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1219 (Path with Maximum Gold)?

This page provides optimized solutions for LeetCode problem 1219 (Path with Maximum Gold) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1219 (Path with Maximum Gold)?

The time complexity for LeetCode 1219 (Path with Maximum Gold) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1219 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1219 in Java, C++, or Python.

Back to LeetCode Solutions