Cherry Pickup LeetCode

The Cherry Pickup problem involves locating the maximum number of cherries that can be collected by two people starting at opposite ends of a grid and moving toward one another. In this Answer, we’ll evaluate the problem statement and provide a solution in Python.

Problem statement

We’re provided an n x n grid that represents a garden where each cell contains some cherries. We need to find the maximum number of cherries that can be collected while following these rules:

The person starts at (0,0) and reaches (n-1,n-1).
When a person encounters a cherry in the cell, they pick it up.
No cherries can be collected without a valid pathA valid path is one that is connected from start to finish without encountering any thorns. between the start and end.

Each cell can have one of the following three values:

0: The cell is empty, and the person can walk through.
1: There is a cherry the user can pick up and pass through.
-1: There is a thorn that blocks the person’s path.

The two rules of traversal are:

Move right or down from the start (0, 0) to the end (n-1, n-1)
Move left or up from the end (n-1, n-1) to the start (0, 0).

An example of this garden grid is illustrated below:

Which of the following correctly defines the rules for the Cherry Pickup problem on an n x n grid?

Two people start at opposite ends of the grid and collect cherries along a path. The maximum number of cherries picked determines the solution.

Starting at (0,0) and reaching (n-1,n-1), a person collects cherries in cells marked 1, avoiding thorns marked -1.

The person starts at (n-1,n-1) and moves to (0,0), collecting cherries and avoiding thorns.

Cherries are collected by one person, starting at any cell, moving in any direction, and summing the cherries encountered.

Algorithm

Imagine we have two robots tasked with picking cherries from the grid. The robots start at the top-left corner and must move to the bottom-right corner, maximizing their cherry collection.

The algorithm maximizes cherry (represented by 1) collection while navigating obstacles represented by -1. We will employ a dynamic programming approach.

Initialize a 3D table (dictionary) to store calculated results.
Define a helper function (table) to:
1. Consider the possible movements of two robots.
2. Recursively explore their paths.
3. Handle boundaries or obstacles by returning a large negative value.
4. Return the cherry count at the bottom-right corner.
Evaluate potential moves for both individuals, counting cherries collected.
Explore four movements
1. Both right
2. One down, one right
3. One right, one down
4. Both down
Select the maximum cherry count among these moves.
Store the maximum cherry count in the dictionary.

Let's see this algorithm in action.

def cherryPickup(garden):
    n = len(garden)  # Get the dimensions of the garden (assumed to be square)
    dictionary = [[[-float('inf')] * n for _ in range(n)] for _ in range(n)]  # Initialize a 3D table (dictionary) with -infinity to store cherry counts at each position for both robots
    def table(x1, y1, x2): # Define a recursive helper function (table) to explore paths
        y2 = x1 + y1 - x2  # Calculate the y-coordinate of the second robot based on the constraint x1 + y1 = x2 + y2
        
        # Base cases: out of bounds, obstacle, or reached the goal
        if x1 == n or y1 == n or x2 == n or y2 == n or garden[x1][y1] == -1 or garden[x2][y2] == -1:
            return -1000000  # Return a very low value for invalid paths or paths hitting obstacles
        if x1 == y1 == x2 == n - 1:  # Reached the bottom-right corner
            return garden[x1][y1]  # Return the cherry count at the final position
        
        if dictionary[x1][y1][x2] != -float('inf'):  # If this state has been visited before
            return dictionary[x1][y1][x2] 
        
        res = garden[x1][y1]  # Cherry count at the current position of the first robot
        if x1 != x2:  # If the robots are not on the same square
            res += garden[x2][y2]  # Add the cherry count of the second robot's position
        nextitem = max(
            table(x1, y1 + 1, x2 + 1),  # Both robots move right
            table(x1 + 1, y1, x2 + 1),  # First robot down, second robot right
            table(x1, y1 + 1, x2),      # First robot right, second robot down
            table(x1 + 1, y1, x2)       # Both robots move down
        ) 
        dictionary[x1][y1][x2] = res + nextitem  # Store the result in the dictionary
        return dictionary[x1][y1][x2]  # Return the calculated maximum cherry count
    result = max(0, table(0, 0, 0)) # Start the search from the top-left corner, Ensure the result is non-negative (0 if no valid path)
    return result
garden = [[0,1,-1],[1,0,-1],[1,1,1]]
print(cherryPickup(garden))

Code explanation

The explanation is as follows:

Line 1: We define the cherryPickup function, which takes garden (n x n grid of cherries) as a parameter.
Line 2: The n stores the size of the garden.
Line 3: This is a 3D list with the initial values. The -float('inf') is applied to the areas not visited yet.
Lines 5: The helper function table that calculates the maximum number of cherries that can be collected.
Lines 8–9: We check if it’s encountering a thorn. If it does, it returns a very negative value -1000000.
Lines 12–13: If the current position is at the bottom-right corner of the garden, it means we’ve reached the end, and the function returns the number of cherries.
Lines 15–16: If we’ve already computed this and stored in dictionary, we return that cached result.
Line 17: Otherwise, we calculate the result in the current cell.
Lines 19–20: We check if positions are equal. If they aren’t, add the number to res.
Lines 22–27: We calculate res for the next four possible moves.
Line 32: We return the final result.
Lines 34–35: This is the code to call the function.

Time complexity

The time complexity of this problem is $O(n^{3})$ , where n is the size of the garden. This complexity arises from initializing a 3D table in $O(n^{3})$ and recursively exploring paths in the garden’s dimensions, evaluating up to four moves at each step.

Space complexity

The space complexity of this problem is $O(n^{3})$ . This is due to the 3D dictionary array, which stores intermediate results for subproblems in $n \ \text{x} \ n \ \text{x} \ n$ space, where $n$ represents the size of the garden.

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments