Cherry Pickup II

Hard

Amazon

2 views

Topics:

ArraysDynamic Programming

You are given a rows x cols matrix grid representing a field of cherries where grid[i][j] represents the number of cherries that you can collect from the (i, j) cell.

You have two robots that can collect cherries for you:

Robot #1 is located at the top-left corner (0, 0), and
Robot #2 is located at the top-right corner (0, cols - 1).

Return the maximum number of cherries collection using both robots by following the rules below:

From a cell (i, j), robots can move to cell (i + 1, j - 1), (i + 1, j), or (i + 1, j + 1). The robots must stay within the bounds of the grid at all times.
When any robot passes through a cell, It picks up all cherries, and the cell becomes an empty cell.
When both robots stay in the same cell, only one takes the cherries.
Both robots should reach the bottom row in grid.

For example:

grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]

In this case, the maximum number of cherries that can be collected is 24.

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

In this case, the maximum number of cherries that can be collected is 28.

What algorithm can you use to solve this problem?

Cherry Pickup II

Hard

Amazon

2 views

Topics:

ArraysDynamic Programming

You are given a rows x cols matrix grid representing a field of cherries where grid[i][j] represents the number of cherries that you can collect from the (i, j) cell.

You have two robots that can collect cherries for you:

Robot #1 is located at the top-left corner (0, 0), and
Robot #2 is located at the top-right corner (0, cols - 1).

Return the maximum number of cherries collection using both robots by following the rules below:

From a cell (i, j), robots can move to cell (i + 1, j - 1), (i + 1, j), or (i + 1, j + 1). The robots must stay within the bounds of the grid at all times.
When any robot passes through a cell, It picks up all cherries, and the cell becomes an empty cell.
When both robots stay in the same cell, only one takes the cherries.
Both robots should reach the bottom row in grid.

For example:

grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]

In this case, the maximum number of cherries that can be collected is 24.

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

In this case, the maximum number of cherries that can be collected is 28.

What algorithm can you use to solve this problem?

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 and constraints of the grid (number of rows and columns)? Are there maximum values for these dimensions?
Can a cell contain a negative cherry value, or can it only be 0 or positive?
What should I return if it's impossible for the robots to reach the bottom row (e.g., the grid is empty or the robots get stuck)? Should I return 0?
Do both robots start at the top row (row 0), and if so, are they guaranteed to start at different columns?
If both robots happen to land on the same cell, should I add the cherry value from that cell only once when calculating the total cherries picked?

Brute Force Solution

Approach

The cherry pickup problem asks us to find the most cherries two people can collect while walking through a grid. A brute force approach involves exploring every possible path each person could take and calculating the cherries they collect along the way.

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

Imagine person one starts at the top-left and person two starts at the top-right of the grid.
At each step, each person can move down, or diagonally down-left, or diagonally down-right.
We need to try every single possible combination of moves for both people until they both reach the bottom row.
For each combination of paths, calculate the total number of cherries collected, remembering that if both people are on the same cell, the cherry is only counted once.
Keep track of the maximum number of cherries collected across all possible combinations of paths.
After exploring all paths, the maximum number of cherries we tracked represents the solution.

Code Implementation

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

    def find_max_cherries(row, first_robot_column, second_robot_column):
        # Base case: Reached the bottom row.
        if row == rows:
            return 0

        max_cherries = 0

        # Iterate through all possible moves for both robots.
        for first_robot_move in [-1, 0, 1]:
            for second_robot_move in [-1, 0, 1]:
                new_first_robot_column = first_robot_column + first_robot_move
                new_second_robot_column = second_robot_column + second_robot_move

                # Check if the new columns are within bounds.
                if 0 <= new_first_robot_column < columns and 0 <= new_second_robot_column < columns:
                    # Calculate the cherries collected in the current cell.
                    cherries = grid[row][new_first_robot_column]
                    if new_first_robot_column != new_second_robot_column:
                        cherries += grid[row][new_second_robot_column]

                    # Recursively calculate the maximum cherries from the next row.
                    cherries += find_max_cherries(row + 1, new_first_robot_column, new_second_robot_column)
                    max_cherries = max(max_cherries, cherries)

        return max_cherries

    # Start both robots at the top row, robot 1 at top-left and robot 2 at top-right
    return find_max_cherries(0, 0, columns - 1)

Big(O) Analysis

Time Complexity

O(3^(2*rows)) – The brute force approach explores every possible path for both robots. Each robot has 3 possible moves (down, diagonally down-left, diagonally down-right) at each step. Since there are 'rows' number of rows, each robot makes 'rows' moves. Therefore, each robot has 3^rows possible paths. Since we have two robots, we must consider all possible combinations of their paths, resulting in 3^rows * 3^rows = 3^(2*rows) combinations. Thus the overall time complexity is O(3^(2*rows)).

Space Complexity

O(3^N) – The brute force approach explores every possible path for both people. At each step, each person has 3 possible moves (down, down-left, down-right). Since there are two people, the number of path combinations grows exponentially. In the worst-case scenario, where N represents the number of rows in the grid, the recursion stack can grow to a depth of N, and at each level, we potentially explore 3 * 3 = 9 branches. Thus the space needed is approximately equal to 3^N due to the recursion call stack and storing intermediate results of all possible paths. The space required to store the path combinations therefore scales as O(3^N).

Optimal Solution

Approach

The best way to solve this is to think about it dynamically, avoiding redundant calculations. Instead of trying all possible paths for both robots, we'll remember the best cherry count we can achieve from each location and reuse that information.

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

Imagine both robots starting at the top-left and top-right corners of the cherry field.
Figure out the possible moves: each robot can move diagonally down to the left, straight down, or diagonally down to the right.
Think about overlapping paths: if both robots end up in the same row, the number of cherries they can collect from there onwards depends only on their current positions.
Create a grid to remember the maximum number of cherries you can collect when the robots are in a particular row with a certain arrangement.
Fill the grid from top to bottom, making decisions based on which move from the row above yielded the most cherries. Consider what each robot picked up during the current move.
When both robots happen to be in the same spot, make sure to only count those cherries once.
The final answer will be found in the bottom row of the grid.

Code Implementation

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

    # Store the max cherries collected at each state.
    maximum_cherries = [[[-1] * columns for _ in range(columns)] for _ in range(rows)]

    def get_max_cherries(row, robot_one_column, robot_two_column):
        if row == rows:
            return 0

        if robot_one_column < 0 or robot_one_column >= columns or \
           robot_two_column < 0 or robot_two_column >= columns:
            return float('-inf')

        if maximum_cherries[row][robot_one_column][robot_two_column] != -1:
            return maximum_cherries[row][robot_one_column][robot_two_column]

        cherries = 0
        if robot_one_column == robot_two_column:
            cherries = grid[row][robot_one_column]
        else:
            cherries = grid[row][robot_one_column] + grid[row][robot_two_column]

        # Explore all possible moves for both robots.
        max_next_cherries = 0
        for robot_one_move in [-1, 0, 1]:
            for robot_two_move in [-1, 0, 1]:
                next_robot_one_column = robot_one_column + robot_one_move
                next_robot_two_column = robot_two_column + robot_two_move

                # Recursively calculate the max cherries from the next row.
                next_cherries = get_max_cherries(row + 1, next_robot_one_column, next_robot_two_column)
                max_next_cherries = max(max_next_cherries, next_cherries)

        maximum_cherries[row][robot_one_column][robot_two_column] = cherries + max_next_cherries

        return maximum_cherries[row][robot_one_column][robot_two_column]

    # Start the robots at the top corners.
    return get_max_cherries(0, 0, columns - 1)

Big(O) Analysis

Time Complexity

O(rows * cols * cols) – The solution uses dynamic programming to fill a 3D grid (rows x cols x cols) where rows represents the number of rows in the cherry field and cols represents the number of columns. We iterate through each row. For each row, we iterate through all possible column positions for robot A and robot B. For each combination of row, robot A's column, and robot B's column, we consider up to 9 possible moves (3 moves for robot A and 3 moves for robot B). Thus, the time complexity is driven by iterating through the rows and all possible column pairs, resulting in O(rows * cols * cols) operations.

Space Complexity

O(rows * cols * cols) – The algorithm uses a grid (or a 2D array) to store the maximum number of cherries that can be collected with the robots at particular row and column positions, described as remembering "the maximum number of cherries you can collect when the robots are in a particular row with a certain arrangement." Since the grid has rows corresponding to the number of rows in the input grid and columns representing possible positions for the two robots (col * col combinations, since both robots can be in any column). This grid has dimensions rows * cols * cols. Therefore the auxiliary space complexity is O(rows * cols * cols), where rows is the number of rows and cols is the number of columns in the input grid.

Edge Cases

Case	How to Handle
Null or empty grid	Return 0 immediately as no cherries can be collected from an empty grid.
Grid with only one row	The two robots start at (0,0) and (0, n-1), so sum the cherry values if distinct, else just the value at that column.
Grid with only one column	The robots will always be at the same position, so the collected cherries equals the sum of all cells in the column.
Maximum grid size (e.g., 70x70) and whether DP scales efficiently	Ensure that DP table dimensions are properly initialized and the algorithm does not exceed time limits.
Grid containing negative numbers	Handle by ensuring the problem statement defines the values of the cherries are non-negative and that a constraint is added to prohibit negative numbers.
Integer overflow when summing cherries	Use appropriate data types (e.g., long) to prevent integer overflow when summing cherry values.
All cells have zero cherries	The result should be 0, and the algorithm needs to ensure it handles this corner case by providing a base case of 0
Robots meet at the same cell with cherries	The solution must only count the cherries from that cell once when robots occupy the same location.