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

Cherry Pickup

Number: 741

Difficulty: Hard

Paid? No

Companies: Google, Snowflake, Atlassian, Cisco, Zomato, Amazon, MathWorks, Akuna Capital

Problem Description

Given an n x n grid where each cell is either 0 (empty), 1 (cherry), or -1 (thorn), the goal is to collect the maximum cherries possible. Start at (0,0) and move to (n-1,n-1) by only moving right or down. Then, return to (0,0) by moving left or up. When a cherry is collected, the cell becomes 0. If there is no valid path between (0,0) and (n-1,n-1), return 0.

Key Insights

  • Transforming the two trips (out and back) into one simultaneous traversal by having two agents start at (0,0) and move to (n-1,n-1) concurrently.
  • Since both agents make the same number of moves, their positions satisfy r1+c1 = r2+c2, which allows reducing the state dimension.
  • Use dynamic programming with a 3-dimensional state (r1, c1, r2) while computing c2 as (r1+c1-r2).
  • Avoid double counting the cherry if both agents land on the same cell.
  • Return 0 if no valid path exists (i.e. if the computed maximum is negative).

Space and Time Complexity

Time Complexity: O(n^3) where n is the grid dimension. Space Complexity: O(n^3) for the DP memoization table.

Solution

The solution employs a dynamic programming approach by simulating two agents moving simultaneously from the start to the destination. Each state is defined by (r1, c1, r2) with c2 computed from the invariant r1+c1 = r2+c2. The algorithm explores all the valid combinations of right and down moves for both agents. When both agents are on the same cell, its cherry (if present) is only counted once. If any move leads to an invalid cell or a thorn, that path is considered as -infinity. A memoization table caches computed states to avoid redundant calculations. The final answer is the maximum cherries collected along the optimal path from start to finish, or 0 if no valid path exists.

Code Solutions

def cherryPickup(grid):
    n = len(grid)
    memo = {}

    def dp(r1, c1, r2):
        c2 = r1 + c1 - r2  # Because steps taken are the same: r1+c1 = r2+c2.
        # Check for out-of-bound indices or thorns.
        if r1 >= n or c1 >= n or r2 >= n or c2 >= n or grid[r1][c1] == -1 or grid[r2][c2] == -1:
            return float('-inf')
        # If reached destination.
        if r1 == n - 1 and c1 == n - 1:
            return grid[r1][c1]
        # Check memoization table.
        if (r1, c1, r2) in memo:
            return memo[(r1, c1, r2)]
        result = grid[r1][c1]
        # Avoid double counting if both agents are on the same cell.
        if r1 != r2 or c1 != c2:
            result += grid[r2][c2]
        # Explore next moves: down/down, right/right, down/right, right/down.
        temp = max(
            dp(r1 + 1, c1, r2 + 1),
            dp(r1, c1 + 1, r2),
            dp(r1 + 1, c1, r2),
            dp(r1, c1 + 1, r2 + 1)
        )
        result += temp
        memo[(r1, c1, r2)] = result
        return result

    ans = dp(0, 0, 0)
    return max(ans, 0)

# Example usage:
grid = [[0, 1, -1], [1, 0, -1], [1, 1, 1]]
print(cherryPickup(grid))  # Expected output: 5
← Back to All Questions