Path with Maximum Gold

Medium

Google

4 views

Topics:

RecursionGraphsDynamic Programming

You are given a gold mine grid of size m x n, where 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.

For example:

grid = [[0,6,0],[5,8,7],[0,9,0]]

The correct output is 24 because the optimal path to get the maximum gold is 9 -> 8 -> 7.

Another example:

grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]

In this case, the correct output is 28. The optimal path is 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7.

How would you approach this problem? Consider the constraints: 1 <= m, n <= 15, and 0 <= grid[i][j] <= 100. There are at most 25 cells containing gold.

Path with Maximum Gold

Medium

Google

4 views

Topics:

RecursionGraphsDynamic Programming

You are given a gold mine grid of size m x n, where 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.

For example:

grid = [[0,6,0],[5,8,7],[0,9,0]]

The correct output is 24 because the optimal path to get the maximum gold is 9 -> 8 -> 7.

Another example:

grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]

In this case, the correct output is 28. The optimal path is 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7.

How would you approach this problem? Consider the constraints: 1 <= m, n <= 15, and 0 <= grid[i][j] <= 100. There are at most 25 cells containing gold.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the grid, and what is the maximum size of the grid?
Can the gold values in the grid be zero? Can they be negative?
What should I return if there is no valid path to collect any gold (e.g., if the grid is empty or all cells are zero)?
Once a cell is visited, can I revisit it during the path (i.e., can I backtrack)?
Are all the gold values integers?

Brute Force Solution

Approach

The brute force method in this scenario involves exploring every possible path through the gold mine. We start at each possible location and try every possible route, collecting gold along the way. Ultimately, we'll pick the path that gives us the most gold.

Here's how the algorithm would work step-by-step:

Start at one location in the mine.
From that location, explore all possible adjacent locations you can move to.
At each of those adjacent locations, again explore all possible adjacent locations you can move to, excluding the location you just came from.
Keep moving and collecting gold along each path until you hit a dead end where you can't move to any new locations with gold.
Keep track of the amount of gold you collected for each path.
Repeat this process, starting at every possible location in the mine.
Compare the total gold collected for all paths starting from all locations and select the maximum amount.

Code Implementation

def get_maximum_gold(grid): 
    rows = len(grid)
    columns = len(grid[0])
    maximum_total_gold = 0

    def explore_path(row, column, current_gold, visited): 
        if row < 0 or row >= rows or column < 0 or column >= columns or grid[row][column] == 0 or (row, column) in visited:
            return current_gold

        current_gold += grid[row][column]
        visited = set(visited)
        visited.add((row, column))
        
        # Explore all 4 possible directions
        up = explore_path(row - 1, column, current_gold, visited)
        down = explore_path(row + 1, column, current_gold, visited)
        left = explore_path(row, column - 1, current_gold, visited)
        right = explore_path(row, column + 1, current_gold, visited)
        
        return max(up, down, left, right)

    # Iterate through each cell in the grid
    for row in range(rows): 
        for column in range(columns): 
            # Only start exploring from cells with gold
            if grid[row][column] != 0:
                maximum_total_gold = max(maximum_total_gold, explore_path(row, column, 0, set()))

    # Start exploration from the current cell
    return maximum_total_gold

Big(O) Analysis

Time Complexity

O(4^(m*n)) – The algorithm explores all possible paths starting from each cell in the m x n grid. In the worst-case scenario, each cell has up to 4 neighbors. The algorithm recursively explores these neighbors, creating a branching factor of up to 4 at each step. Since the longest possible path is bounded by the total number of cells (m*n), the time complexity grows exponentially with a factor of 4 for each cell visited in the path. Therefore, the overall time complexity is approximately O(4^(m*n)).

Space Complexity

O(M*N) – The provided brute force approach utilizes recursion to explore every possible path in the gold mine. The maximum depth of the recursion is bounded by the number of cells in the grid, where M is the number of rows and N is the number of columns. In the worst case, the recursion stack could grow to a depth of M*N, representing a path visiting every cell in the grid. Furthermore, a visited set of size M*N is used to keep track of visited cells during each path exploration to prevent cycles. Therefore, the space complexity is O(M*N).

Optimal Solution

Approach

The challenge is to find the most gold you can collect by walking through a grid. The best way to solve it is by exploring all possible paths from each starting point and remembering the best amount of gold collected from each location to avoid repeating work.

Here's how the algorithm would work step-by-step:

Consider each location with gold as a possible starting point for a path.
From each starting location, explore all four possible directions (up, down, left, right) as long as you stay within the grid and find a cell with gold.
As you move along a path, keep track of the total amount of gold collected.
When you reach a dead end (no more adjacent cells with gold) or revisit a location, compare the total gold collected on that path to the maximum gold you've seen before from that location.
Store the maximum gold for that location. This prevents re-calculating the best path from that location later.
Once you've explored all possible paths from all starting locations, the largest amount of gold you've found is the answer.

Code Implementation

def get_maximum_gold(grid):    rows = len(grid)
    cols = len(grid[0])
    max_gold_collected = 0

    def explore_path(row, col, current_gold_total, visited):
        nonlocal max_gold_collected

        # Update maximum gold if current path is better.
        max_gold_collected = max(max_gold_collected, current_gold_total)

        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        for delta_row, delta_col in directions:
            new_row = row + delta_row
            new_col = col + delta_col

            # Check boundaries and if cell is valid to explore.
            if 0 <= new_row < rows and 0 <= new_col < cols and \
               grid[new_row][new_col] != 0 and (new_row, new_col) not in visited:

                # Recursively explore the path.
                explore_path(new_row, new_col, current_gold_total + grid[new_row][new_col], visited | {(new_row, new_col)})

    # Iterate to find a starting point to explore.
    for row in range(rows):
        for col in range(cols):
            if grid[row][col] != 0:
                # Start exploring from the current valid cell.
                explore_path(row, col, grid[row][col], {(row, col)})

    return max_gold_collected

Big(O) Analysis

Time Complexity

O(m * n * 4^(m*n)) – The algorithm iterates through each cell of the m x n grid as a potential starting point, resulting in O(m * n) starting points. From each starting point, it explores all possible paths using recursion. In the worst-case scenario, each cell could have gold, and the algorithm might explore all possible paths of length up to m * n. Since each cell has four possible directions to explore, the number of paths from each starting point can grow exponentially, up to 4^(m*n) in the worst case. Therefore, the overall time complexity is O(m * n * 4^(m*n)).

Space Complexity

O(M * N) – The auxiliary space is primarily determined by the recursion stack and the 'visited' locations. In the worst-case scenario, the recursion depth could potentially visit every cell in the grid before hitting a dead end, which is proportional to the number of cells in the grid. Additionally, to avoid revisiting cells, we implicitly maintain a 'visited' set, which in the worst case, stores all cells. Therefore, the space complexity is O(M * N), where M is the number of rows and N is the number of columns in the grid.

Edge Cases

Case	How to Handle
Null or empty grid	Return 0 immediately as there's no grid to traverse.
Grid with single cell containing 0	Return 0 as no gold can be collected from that cell.
Grid with single cell containing positive gold	Return the cell's gold value since it is the maximum possible.
Grid with all cells containing 0	Return 0 as no gold can be collected.
Grid with large dimensions (maximum size constraints)	Ensure the recursive calls do not exceed stack limits, potentially use iterative DFS instead for scalability.
Grid contains high gold values, potentially causing integer overflow when summing the path	Use a larger data type (e.g., long) to store the path sum if necessary to prevent overflow.
Disconnected graph where no path can reach all gold mines	The DFS approach explores all possible paths from each starting point so will find the optimal path even if disconnected.
Multiple paths with the same maximum gold value exist	The algorithm finds one of the paths with maximum gold and returns that value, so it doesn't need to consider every maximum path.