We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Path with Maximum Gold

Number: 1331

Difficulty: Medium

Paid? No

Companies: Amazon, Google

Problem Description

Given a grid representing a gold mine, find the maximum amount of gold you can collect. You can start and stop at any cell that contains gold, move up, down, left, or right, and every time you step into a cell you collect its gold. You cannot revisit a cell and cannot step on a cell with 0 gold.

Key Insights

  • Use Depth First Search (DFS) with backtracking to explore all possible paths.
  • Since you cannot revisit a cell, mark a cell as visited temporarily to avoid cycles.
  • Start DFS from each cell containing gold to cover all potential paths.
  • The small grid size and limited gold cells (at most 25) make the recursive approach feasible.
  • Backtracking is crucial: restore the cell's gold after exploring each path to allow other paths to use the cell.

Space and Time Complexity

Time Complexity: Exponential in the worst-case (O(4^(number of gold cells))) due to exploring all paths. Space Complexity: O(m * n) for the recursion stack in the worst-case scenario.

Solution

The solution uses DFS with backtracking. For each cell with positive gold, initiate a DFS that:

  1. Collects the gold and marks the cell as visited (by setting it to 0).
  2. Recursively explores all four adjacent cells that are within bounds and contain gold.
  3. Updates a global maximum sum with the running total.
  4. Restores the cell’s original gold value on returning (backtracking) to allow exploration of other paths. This approach ensures every path is considered, and the best outcome is recorded.

Code Solutions

# Function to get the maximum amount of gold from the grid.
def getMaximumGold(grid):
    rows, cols = len(grid), len(grid[0])
    max_gold = 0

    # DFS function to explore paths starting at cell (i, j)
    def dfs(i, j, current_sum):
        nonlocal max_gold
        # Update the global maximum gold collected.
        max_gold = max(max_gold, current_sum)
        # Save the current value and mark this cell as visited.
        temp = grid[i][j]
        grid[i][j] = 0
        
        # Explore adjacent cells in four directions.
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            new_i, new_j = i + dx, j + dy
            if 0 <= new_i < rows and 0 <= new_j < cols and grid[new_i][new_j] != 0:
                dfs(new_i, new_j, current_sum + grid[new_i][new_j])
        
        # Backtrack: restore the original value of this cell.
        grid[i][j] = temp

    # Start DFS from every cell containing gold.
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] != 0:
                dfs(i, j, grid[i][j])
                
    return max_gold

# Example usage
if __name__ == "__main__":
    grid = [[0,6,0], [5,8,7], [0,9,0]]
    print(getMaximumGold(grid))  # Expected output: 24
← Back to All Questions