1219. Path with Maximum Gold

MediumArrayBacktrackingMatrix
Leetcode Link

Problem Description

In this challenge, you are given a two-dimensional grid that represents a gold mine, with each cell containing a certain amount of gold or being empty (indicated by a 0). The objective is to collect as much gold as possible with the following constraints:

  • You can collect gold from any cell and start from there.
  • You may move one step at a time in any of the four cardinal directions (left, right, up, or down).
  • Once you leave a cell, you cannot enter it again; you collect the gold once only.
  • You cannot step into a cell with zero gold.
  • You can end your collection route at any cell containing gold.

Your task is to determine the maximum amount of gold that can be collected following these rules.

Intuition

To solve this problem, we need to explore every possible path that maximizes gold collection, which is a classic Depth-First Search (DFS) scenario. The intuition behind using DFS is that we want to explore all potential routes from each cell containing gold.

The process involves exploring a cell, collecting its gold, and then recursively checking all other paths from its adjacent cells. We keep track of the gold collected along each path and then backtracking, which means restoring the state before the DFS call, to ensure that we can explore other paths from the current cell.

Here's the approach:

  1. Iterate through each cell in the grid.
  2. If a cell has gold, initiate a DFS search from that cell.
  3. Mark the cell as visited by setting its value to 0 to prevent revisiting, and collect the gold.
  4. Explore all four directions recursively, summing up the gold from subsequent cells.
  5. After exploring all directions from the current cell, backtrack by restoring the cell's gold value.
  6. Keep track of the maximum gold collected during each DFS call.
  7. Once all cells have been explored, return the maximum gold collected.

This approach exhaustively searches all possible paths and ensures that we find the maximum amount of gold that can be collected in the mine.

Learn more about Backtracking patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Solution Approach

The implementation uses Depth-First Search (DFS), a recursive algorithm that exhaustively searches through all possible paths in the grid. Here's a breakdown of how the DFS is implemented in the provided solution:

  • A helper function dfs(i, j) is defined to perform the DFS search from the cell at row i and column j.
  • The function first checks if the current cell (i, j) is out of bounds or if it contains 0 gold, in which case it returns 0 since no gold can be collected.
  • If the cell contains gold, the function temporarily sets the gold amount to zero (grid[i][j] = 0). This serves as marking the cell as visited to avoid revisiting it in this path.
  • The function then recursively explores the four adjacent cells (left, right, up, and down) by calling dfs(i + a, j + b) for each direction and adds the result to the current gold value. The max() function is used to choose the path that yields the maximum gold from these recursive calls.
  • After exploring all directions, the function backtracks by resetting the gold value of the current cell (grid[i][j] = t) to ensure that future DFS calls can visit this cell from a different starting point.
  • The main function iterates over every cell in the grid and calls dfs(i, j) if the cell contains gold, thereby initiating the DFS search from that cell.
  • Each call to dfs(i, j) will return the maximum amount of gold that can be collected starting from that cell, and the overall maximum is updated accordingly.
  • The built-in max() function is applied across all cells to find the single highest gold value collected.

The data structures used in this approach are:

  • The input grid itself, which is a 2-dimensional list.
  • Temporary variables for storing the current gold amount and for carrying out the DFS.

By using recursive DFS, the solution is able to explore all paths optimally without the need for additional data structures to track visited cells or paths, since the grid is modified in place and later restored during backtracking.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

Example Walkthrough

Let's illustrate the solution approach using a small example of a gold mine grid:

14 2
23 0

We want to collect the maximum amount of gold following the given rules.

Here is a step-by-step walkthrough of the solution implemented with DFS:

  1. We start our search with the cell at the top-left corner (0,0) which contains 4 gold. We initiate DFS from this cell.

  2. We collect the 4 gold from this cell and mark it as visited by setting its value to 0. Our grid now looks like this:

    10 2
23 0

    The total gold collected is 4.

  3. From here, we can move right or down. Moving right, we find 2 gold. We collect it and mark the cell as visited, updating the grid:

    10 0
23 0

    Now we have 4 + 2 = 6 gold.

  4. Since we can't move into a cell with zero gold, we backtrack and restore the gold value of the cell (0,1). Our grid is back to:

    10 2
23 0

    And we explore the next direction, which is down, finding 3 gold in cell (1,0).

  5. We repeat the process for cell (1,0): collect the 3 gold, mark the cell as visited, and update the grid:

    10 2
20 0

    The total gold now is 4 + 3 = 7.

  6. Now, we cannot move any further from cell (1,0), so we finish this path and record that we've collected 7 gold as our current maximum.

  7. After that, we backtrack, restoring the grid, and continue the process for the remaining cells. The grid is restored to its previous state:

    14 2
23 0

    Since there's only one other cell with gold we haven't started from (1,0), we move there and repeat the DFS process.

  8. We try moving from cell (1,0) with 3 gold, but since the adjacent cells with gold have already been visited in previous iterations, there's no further gold to collect.

  9. Our record shows the maximum gold collected was 7 gold from the path that started at (0,0), moved to (1,0), and then to (0,1).

So, the maximum amount of gold that can be collected in this example, following the DFS approach we outlined in the solution, is 7.

Solution Implementation

1class Solution:
2    def get_maximum_gold(self, grid):
3        """
4        Performs a depth-first search to find the maximum gold that can
5        be collected starting from any point in the grid.
6      
7        :param grid: List[List[int]] representing the grid of cells with gold.
8        :return: int representing the maximum amount of gold that can be collected.
9        """
10      
11        def dfs(x, y):
12            """
13            Depth-first search helper function starting from cell (x, y).
14            The idea is to try all possible paths and get the maximum gold.
15
16            :param x: int representing the x-coordinate of the current cell.
17            :param y: int representing the y-coordinate of the current cell.
18            :return: int representing the collected gold amount via the path.
19            """
20            # Check if the current position is out of bounds or has no gold
21            if not (0 <= x < rows and 0 <= y < cols and grid[x][y]):
22                return 0
23          
24            # Store the gold at the current position and mark this cell as visited by setting the gold to 0
25            gold = grid[x][y]
26            grid[x][y] = 0
27          
28            # Calculate the gold gathered in all four directions
29            total_gold = gold + max(
30                dfs(x + dx, y + dy) for dx, dy in directions
31            )
32          
33            # Backtrack and reset the gold to original since we might visit this cell again via a different path
34            grid[x][y] = gold
35            return total_gold
36
37        # Initialize the number of rows and columns of the grid
38        rows, cols = len(grid), len(grid[0])
39
40        # Define all four possible directions to move on the grid, which are right, left, up, and down
41        directions = [(0, 1), (0, -1), (-1, 0), (1, 0)]
42      
43        # Using a grid comprehension, perform depth-first search starting from each cell
44        # and return the maximum gold found in all the paths
45        return max(dfs(x, y) for x in range(rows) for y in range(cols))
46
47# The modified class and function names now follow PEP 8 naming conventions.
48
1class Solution {
2    private int[][] grid; // Holds the grid with gold amounts
3    private int rows;     // Number of rows in the grid
4    private int cols;     // Number of columns in the grid
5
6    // Computes the maximum gold that can be collected
7    public int getMaximumGold(int[][] grid) {
8        // Initialize rows and cols based on the input grid size
9        rows = grid.length;
10        cols = grid[0].length;
11        this.grid = grid; // Assign the grid
12        int maxGold = 0;  // Initialize maximum gold collected
13
14        // Iterate over all cells of the grid
15        for (int i = 0; i < rows; ++i) {
16            for (int j = 0; j < cols; ++j) {
17                // Update maxGold with the maximum of the current maxGold or the gold collected by DFS from this cell
18                maxGold = Math.max(maxGold, dfs(i, j));
19            }
20        }
21        return maxGold; // Return the maximum gold collected
22    }
23
24    // Helper method for depth-first search
25    private int dfs(int row, int col) {
26        // Base case: If the cell is out of the grid bounds or has 0 gold, return 0
27        if (row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] == 0) {
28            return 0;
29        }
30        // Store gold value of the current cell
31        int gold = grid[row][col];
32        // Mark the current cell as visited by setting gold to 0
33        grid[row][col] = 0;
34
35        // Array to facilitate iteration over the adjacent cells (up, right, down, left)
36        int[] directions = {-1, 0, 1, 0, -1};
37        int maxGold = 0; // Initialize max gold collected from this cell
38
39        // Iterate over all adjacent cells
40        for (int k = 0; k < 4; ++k) {
41            // Calculate the gold collected by DFS of the adjacent cells and update maxGold accordingly
42            maxGold = Math.max(maxGold, gold + dfs(row + directions[k], col + directions[k + 1]));
43        }
44        // Backtrack: reset the value of the cell to the original gold amount
45        grid[row][col] = gold;
46
47        // Return the maximum gold that can be collected from this cell
48        return maxGold;
49    }
50}
51
1#include <vector>
2#include <algorithm>  // include algorithm library for using max function
3
4class Solution {
5public:
6    // Directions array representing the 4 possible movements: up, right, down, left.
7    std::vector<int> directions = {-1, 0, 1, 0, -1};
8
9    // Main function to call for getting the maximum gold.
10    int getMaximumGold(std::vector<std::vector<int>>& grid) {
11        int maxGold = 0;
12      
13        // Iterate over each cell in the grid.
14        for (int i = 0; i < grid.size(); ++i) {
15            for (int j = 0; j < grid[0].size(); ++j) {
16                // Compute the maximum gold recursively starting from the current cell.
17                maxGold = std::max(maxGold, dfs(i, j, grid));
18            }
19        }
20      
21        return maxGold;
22    }
23
24private:
25    // Helper DFS function to explore the grid for gold collection.
26    int dfs(int x, int y, std::vector<std::vector<int>>& grid) {
27        // Boundary check and cell with zero gold check
28        if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || grid[x][y] == 0) {
29            return 0;
30        }
31      
32        int gold = grid[x][y];  // Store the gold in the current cell.
33        grid[x][y] = 0;         // Mark the current cell as visited by setting it to 0.
34      
35        int maxGoldFromHere = 0;
36      
37        // Explore all 4 adjacent cells.
38        for (int i = 0; i < 4; ++i) {
39            // Recursively collect the gold by going in one direction.
40            int nextGold = dfs(x + directions[i], y + directions[i + 1], grid);
41            // Update the maximum gold collected from the current path.
42            maxGoldFromHere = std::max(maxGoldFromHere, gold + nextGold);
43        }
44      
45        grid[x][y] = gold;  // Reset the cell to its original gold value.
46      
47        return maxGoldFromHere;  // Return the maximum gold obtained starting from (x, y).
48    }
49};
50
1/**
2 * Retrieves the maximum amount of gold by visiting cells in the grid.
3 * Each cell can be visited only once, and we must avoid cells with 0 gold.
4 * 
5 * @param {number[][]} grid - The grid of cells containing gold amounts.
6 * @return {number} - The maximum amount of gold that can be collected.
7 */
8function getMaximumGold(grid: number[][]): number {
9    const rowCount: number = grid.length;
10    const colCount: number = grid[0].length;
11
12    // The depth-first search function explores all possible paths from the current cell.
13    function dfs(row: number, col: number): number {
14        // Boundary check and gold check, return 0 if it's out of bounds or cell is empty
15        if (row < 0 || row >= rowCount || col < 0 || col >= colCount || grid[row][col] === 0) {
16            return 0;
17        }
18
19        // Temporarily set the current cell to 0 to mark as visited
20        const currentGold: number = grid[row][col];
21        grid[row][col] = 0;
22      
23        let maxGoldFromHere: number = 0;
24      
25        // Directions: up, right, down, left
26        const directions: number[] = [-1, 0, 1, 0, -1];
27      
28        // Explore in all four directions
29        for (let k: number = 0; k < 4; ++k) {
30            const nextRow: number = row + directions[k];
31            const nextCol: number = col + directions[k + 1];
32          
33            // Accumulate the max gold along this path
34            maxGoldFromHere = Math.max(maxGoldFromHere, currentGold + dfs(nextRow, nextCol));
35        }
36
37        // Reset the current cell's value after exploring all paths
38        grid[row][col] = currentGold;
39      
40        return maxGoldFromHere;
41    }
42
43    // Initialize the answer to 0; it will store the maximum gold found
44    let maxGold: number = 0;
45
46    // Start from each cell in the grid to find the maximum gold
47    for (let i: number = 0; i < rowCount; ++i) {
48        for (let j: number = 0; j < colCount; ++j) {
49            maxGold = Math.max(maxGold, dfs(i, j));
50        }
51    }
52
53    return maxGold;
54}
55
Not Sure What to Study? Take the 2-min Quiz：

Depth first search is equivalent to which of the tree traversal order?

Time and Space Complexity

The time complexity of the provided code is calculated based on several factors:

  • The algorithm performs a depth-first search (DFS) starting from each cell that has a positive gold value.
  • Each DFS explores four possible directions to go next (except when on the border or if a cell is already visited).

Let's denote m as the number of rows and n as the number of columns in the grid. In the worst case, the entire grid could be filled with positive gold values, requiring an exhaustive search from each cell.

For each DFS, the maximum depth could be min(m*n) if the path is allowed to traverse every cell. However, due to path restrictions (not revisiting a cell with no gold), the maximum depth will be less than or equal to m*n. Each time we explore a cell, there are at most 4 directions to explore next.

Therefore, an upper bound of the time complexity is O(4^(m*n)), which is exponential due to the recursive exploration with branching.

For space complexity:

  • The space used by the call stack during the recursive DFS would be equal to the maximum depth of the recursion which, in the worst case, is O(m*n) since we might have to traverse the entire grid if it is all filled with gold.
  • We are also modifying the input grid to mark the cells as visited by temporarily setting grid[i][j] = 0 and resetting it back to its original value before returning from the DFS. This in-place modification means we don't use extra space proportional to the grid size (except the implicit recursion stack).

Thus, the space complexity is O(m*n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following problems can be solved with backtracking (select multiple)

Recommended Readings

Backtracking 1

Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

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.

←
↑TA 👨‍🏫