Maximum Coin Collection

Medium

Asked by:

28 views

Topics:

Dynamic ProgrammingArrays

You are given a 2D grid grid representing a board, where each cell contains a certain number of coins. You start at the top-left cell (0, 0) and want to reach the bottom-right cell (m-1, n-1), collecting the maximum number of coins along the way.

You can only move in two directions: right (grid[i][j] to grid[i][j+1]) or down (grid[i][j] to grid[i+1][j]). Your task is to find the maximum number of coins you can collect.

Example 1:

Input: grid = [[1,2,3],[4,5,6],[7,8,9]]
Output: 39
Explanation:
The path that maximizes the coin collection is 1 -> 2 -> 3 -> 6 -> 9, with a total of 1 + 2 + 3 + 6 + 9 = 21.
The path that maximizes the coin collection is 1 -> 4 -> 7 -> 8 -> 9, with a total of 1 + 4 + 7 + 8 + 9 = 29.
Consider the grid [[1,2,3],[4,5,6]]. Path 1 -> 2 -> 3 -> 6 has a total of 1 + 2 + 3 + 6 = 12.
Path 1 -> 4 -> 5 -> 6 has a total of 1 + 4 + 5 + 6 = 16.

Example 2:

Input: grid = [[1,1,1],[1,1,1],[1,1,1]]
Output: 7
Explanation:
Any path from top-left to bottom-right will have the same number of coins collected since all cells contain 1.

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 1000

Try coding it in LeetCode

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 range of values for the coins in each cell? Can coin values be negative, zero, or only positive integers?
Where does the path start and end? Is the starting point always the top-left corner (0, 0) and the ending point always the bottom-right corner (m-1, n-1)?
What moves are allowed? Can I only move right and down, or are other movements like up and left allowed?
If there are multiple paths that yield the same maximum coin collection, do I need to return a specific one or is any one acceptable?
If it is impossible to reach the destination, or if the grid is empty, what should I return (e.g., 0, null, or throw an exception)?

Brute Force Solution

Approach

Imagine you are exploring a maze and want to find the path that gives you the most coins. The brute force method means trying every single possible path through the maze, from start to finish. Then you compare each paths total coins to find the maximum amount.

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

Start at the beginning of the maze.
Consider every possible direction you can go from your current location.
For each direction, pretend you went that way and record how many coins you picked up.
From that new location, again consider every possible direction you can go.
Keep going until you reach the end of the maze for one particular path.
Record the total number of coins you collected on that path.
Go back to the beginning and repeat these steps for every other possible path through the maze.
Finally, compare the total coins for all the paths you tried and choose the path that gave you the most coins.

Code Implementation

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

    def explore_paths(row_position, column_position, current_coins):
        # If we reach the end, return the coins collected
        if row_position == rows - 1 and column_position == cols - 1:
            return current_coins + grid[row_position][column_position]

        if row_position >= rows or column_position >= cols:
            return 0

        current_coins += grid[row_position][column_position]

        # Explore going right
        right_path_coins = 0
        right_path_coins = explore_paths(row_position, column_position + 1, current_coins)

        # Explore going down
        down_path_coins = 0
        down_path_coins = explore_paths(row_position + 1, column_position, current_coins)

        # Return the max coins between going right and down
        return max(right_path_coins, down_path_coins)

    # Start exploring paths from top-left with 0 coins
    maximum_coins = explore_paths(0, 0, 0)
    return maximum_coins

Big(O) Analysis

Time Complexity

O(2^(m+n)) – The brute force approach explores every possible path in the maze. In the worst case, a maze of size m x n allows for two choices (right or down, assuming we can only move in these directions) at each step. Therefore, the number of possible paths can grow exponentially with the sum of the dimensions of the maze (m+n). Consequently, the time complexity is O(2^(m+n)).

Space Complexity

O(N) – The brute force approach explores every possible path in the maze using recursion. In the worst-case scenario, the depth of the recursion can be proportional to N, where N represents the number of steps in the longest possible path (or the total number of cells if every cell is visited once). Each recursive call requires storing information on the call stack (function arguments, local variables, and return address). Therefore, the auxiliary space complexity is O(N) due to the maximum depth of the recursion stack.

Optimal Solution

Approach

The problem asks us to find the best path through a grid to collect the most coins. Instead of trying every possible path, we use a technique that builds up the optimal solution from smaller subproblems. This way, we only need to consider each position in the grid once.

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

Start from the top-left corner of the grid.
For each position, figure out the maximum number of coins we could have collected to reach that position.
To do this, look at the position directly above and the position directly to the left. Whichever of those two positions has the higher coin total, add that total to the number of coins in the current position.
If there's no position above or to the left (because we're on the top row or left column), just use the coin total from the starting position and add it to the coins in the current position.
Repeat this process for every position in the grid, moving from left to right, top to bottom.
Once you reach the bottom-right corner, the number of coins at that position will be the maximum number of coins you can collect following the optimal path.

Code Implementation

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

    # Iterate through the grid to calculate max coins at each position.
    for row_index in range(rows):
        for col_index in range(cols):
            # For the starting point, no changes are needed.
            if row_index == 0 and col_index == 0:
                continue

            max_coins_from_above = 0
            max_coins_from_left = 0

            # Check the cell above if not on the top row
            if row_index > 0:

                max_coins_from_above = grid[row_index - 1][col_index]

            # Check the cell to the left if not on the left column
            if col_index > 0:

                max_coins_from_left = grid[row_index][col_index - 1]

            # Store maximum coins by adding current cell value.
            grid[row_index][col_index] += max(max_coins_from_above, max_coins_from_left)

    # The bottom-right cell contains the maximum possible coins.
    return grid[rows - 1][cols - 1]

Big(O) Analysis

Time Complexity

O(m*n) – The algorithm iterates through each cell of an m x n grid once to compute the maximum coin collection up to that point. For each cell, a constant-time operation (addition and comparison) is performed. Therefore, the time complexity is directly proportional to the number of cells in the grid, resulting in a time complexity of O(m*n), where m is the number of rows and n is the number of columns. If m and n are assumed to be of similar size (e.g., a square grid), we can say that the time complexity approximates O(n*n). This simplifies to O(n²).

Space Complexity

O(1) – The provided solution modifies the input grid in place to store intermediate results. No additional data structures are used beyond a few scalar variables for iteration. Therefore, the auxiliary space required does not scale with the input grid size, making the space complexity constant.

Edge Cases

Case	How to Handle
Null or empty grid	Return 0 if the input grid is null or has zero rows or columns, as no coins can be collected.
Grid with only one row or one column	Handle the case where only a single row or column exists by iterating through that row or column.
Grid with all zero values	Return 0 if all values in the grid are zero, as no coins can be collected.
Grid with negative values	Handle negative values as loss and the algorithm must minimize loss rather than maximizing gain, or throw an exception if negative values are not allowed.
Large grid dimensions (potential memory/performance issues)	Optimize for space complexity to avoid memory overflow with large grids, possibly using dynamic programming with rolling arrays.
Grid with very large coin values (potential integer overflow)	Use a data type with larger capacity, such as long or BigInteger, to prevent integer overflow during calculations.
Path blocked by obstacles (e.g., -1 values representing walls)	Modify the algorithm to skip obstacle cells and avoid calculating paths through them.
Maximum coin value at starting or ending cell	Ensure the algorithm correctly incorporates the coin value at both the starting and ending cells when calculating the optimal path.

Null or empty grid

How to Handle:

Return 0 if the input grid is null or has zero rows or columns, as no coins can be collected.

Grid with only one row or one column

How to Handle:

Handle the case where only a single row or column exists by iterating through that row or column.

Grid with all zero values

How to Handle:

Return 0 if all values in the grid are zero, as no coins can be collected.

Grid with negative values

How to Handle:

Handle negative values as loss and the algorithm must minimize loss rather than maximizing gain, or throw an exception if negative values are not allowed.

Large grid dimensions (potential memory/performance issues)

How to Handle:

Optimize for space complexity to avoid memory overflow with large grids, possibly using dynamic programming with rolling arrays.

Grid with very large coin values (potential integer overflow)

How to Handle:

Use a data type with larger capacity, such as long or BigInteger, to prevent integer overflow during calculations.

Path blocked by obstacles (e.g., -1 values representing walls)

How to Handle:

Modify the algorithm to skip obstacle cells and avoid calculating paths through them.

Maximum coin value at starting or ending cell

How to Handle:

Ensure the algorithm correctly incorporates the coin value at both the starting and ending cells when calculating the optimal path.