Cherry Pickup

Hard

#0695Time: O(N^3). The number of states is N * N * N. Each state `(r1, c1, r2)` is computed once due to memoization.Space: O(N^3), where N is the dimension of the grid. This is for the memoization table `memo[N][N][N]`.7 companies

Patterns

Dynamic Programming

Data structures

Array Matrix

Companies

Atlassian Cisco Flipkart J.P. Morgan

Prompt

You are given an n x n grid representing a field of cherries, each cell is one of three possible integers.

0 means the cell is empty, so you can pass through,
1 means the cell contains a cherry that you can pick up and pass through, or
-1 means the cell contains a thorn that blocks your way.

Return the maximum number of cherries you can collect by following the rules below:

Starting at the position (0, 0) and reaching (n - 1, n - 1) by moving right or down through valid path cells (cells with value 0 or 1).
After reaching (n - 1, n - 1), returning to (0, 0) by moving left or up through valid path cells.
When passing through a path cell containing a cherry, you pick it up, and the cell becomes an empty cell 0.
If there is no valid path between (0, 0) and (n - 1, n - 1), then no cherries can be collected.

Example 1:

Input: grid = [[0,1,-1],[1,0,-1],[1,1,1]]
Output: 5
Explanation: The player started at (0, 0) and went down, down, right right to reach (2, 2).
4 cherries were picked up during this single trip, and the matrix becomes [[0,1,-1],[0,0,-1],[0,0,0]].
Then, the player went left, up, up, left to return home, picking up one more cherry.
The total number of cherries picked up is 5, and this is the maximum possible.

Example 2:

Input: grid = [[1,1,-1],[1,-1,1],[-1,1,1]]
Output: 0

Constraints:

n == grid.length
n == grid[i].length
1 <= n <= 50
grid[i][j] is -1, 0, or 1.
grid[0][0] != -1
grid[n - 1][n - 1] != -1

Approaches

2 approaches with complexity analysis and trade-offs.

A brute-force approach would explore all possible pairs of paths, which is computationally expensive. We can significantly optimize this by using dynamic programming with memoization. The core idea is to rephrase the problem as two people moving from (0,0) to (n-1,n-1) simultaneously. The state can be defined by the coordinates of both people. A crucial observation, r1 + c1 = r2 + c2, allows us to use a 3D state (r1, c1, r2) to represent the system. We use a 3D array to memoize the results of subproblems, avoiding redundant calculations.

Algorithm

The problem of a round trip (down-right then up-left) can be modeled as two people starting at (0, 0) and moving to (n-1, n-1) simultaneously, only moving down or right.
The state of the system can be defined by the coordinates of both people, (r1, c1) and (r2, c2). A key observation is that after the same number of steps, their Manhattan distances from the origin are equal: r1 + c1 = r2 + c2. This allows us to reduce the state to three variables, for instance, (r1, c1, r2), from which c2 can be derived as c2 = r1 + c1 - r2.
We define a recursive function solve(r1, c1, r2) that computes the maximum cherries that can be collected from the current positions (r1, c1) and (r2, c2) to the destination (n-1, n-1).
To avoid recomputing results for the same state, we use a 3D memoization table memo[r1][c1][r2].
The base case for the recursion is when both people reach the destination (n-1, n-1). In this case, we return the value of grid[n-1][n-1].
If any person goes out of bounds or hits a thorn (-1), that path is invalid, and we return a very small number (e.g., Integer.MIN_VALUE) to prune this path.
In each recursive step, we calculate the cherries collected at the current positions. If both people are on the same cell, the cherry is counted only once.
We then make four recursive calls for the next possible combined moves: (down, down), (down, right), (right, down), and (right, right).
The result for the current state is the sum of current cherries and the maximum value returned by the four recursive calls. This result is stored in the memoization table.
The initial call is solve(0, 0, 0). The final answer is max(0, result) because if no path exists, the function will return a negative value, but we should output 0.

Walkthrough

This approach uses a top-down recursive method with a memoization table to store the results of subproblems. The state (r1, c1, r2) represents person 1 at (r1, c1) and person 2 at (r2, c2), where c2 is derived from r1 + c1 - r2. The function calculates the maximum cherries from this state to the end.

1class Solution {2    private int[][][] memo;3    private int[][] grid;4    private int n;5 6    public int cherryPickup(int[][] grid) {7        this.grid = grid;8        this.n = grid.length;9        // Using r1, c1, r2 as state. c2 is derived.10        this.memo = new int[n][n][n];11        for (int i = 0; i < n; i++) {12            for (int j = 0; j < n; j++) {13                // Initialize memo table with -1 to indicate not computed14                java.util.Arrays.fill(memo[i][j], -1);15            }16        }17        18        return Math.max(0, solve(0, 0, 0));19    }20 21    private int solve(int r1, int c1, int r2) {22        int c2 = r1 + c1 - r2;23        24        // Check if paths are valid25        if (r1 >= n || c1 >= n || r2 >= n || c2 >= n || grid[r1][c1] == -1 || grid[r2][c2] == -1) {26            return Integer.MIN_VALUE;27        }28        29        // Base case: reached destination30        if (r1 == n - 1 && c1 == n - 1) {31            return grid[r1][c1];32        }33        34        // Check memoization table35        if (memo[r1][c1][r2] != -1) {36            return memo[r1][c1][r2];37        }38        39        // Calculate cherries at current step40        int cherries = 0;41        if (r1 == r2 && c1 == c2) {42            cherries = grid[r1][c1];43        } else {44            cherries = grid[r1][c1] + grid[r2][c2];45        }46        47        // Explore 4 possible next moves48        int futureCherries = Math.max(49            Math.max(solve(r1 + 1, c1, r2 + 1),  // P1 down, P2 down50                     solve(r1 + 1, c1, r2)),     // P1 down, P2 right51            Math.max(solve(r1, c1 + 1, r2 + 1),  // P1 right, P2 down52                     solve(r1, c1 + 1, r2))      // P1 right, P2 right53        );54        55        // If no valid future path, current path is also invalid56        if (futureCherries == Integer.MIN_VALUE) {57            return memo[r1][c1][r2] = Integer.MIN_VALUE;58        }59        60        // Store and return result61        return memo[r1][c1][r2] = cherries + futureCherries;62    }63}

Complexity

Time

O(N^3). The number of states is N * N * N. Each state `(r1, c1, r2)` is computed once due to memoization.

Space

O(N^3), where N is the dimension of the grid. This is for the memoization table `memo[N][N][N]`.

Trade-offs

Pros

Guaranteed to find the optimal solution.
Much more efficient than brute-force by avoiding recomputation of subproblems.
The recursive structure is often a direct translation of the problem's recurrence relation.

Cons

Requires O(N^3) space for the memoization table, which can be large for bigger N.
Recursive solutions might lead to stack overflow for very deep recursion, although not an issue with N <= 50.

The previous DP approach has a space complexity of O(N^3). We can optimize this by noticing that the computation for the current step k only requires the results from the previous step k-1. This allows us to reduce the space complexity to O(N^2) by using only two 2D arrays to store the DP states for the current and previous steps. This bottom-up iterative approach has the same time complexity but is more memory-efficient.

Algorithm

This approach is the iterative, or bottom-up, version of the DP solution.
We use the state dp[k][r1][r2] representing the maximum cherries after k steps, with person 1 at row r1 and person 2 at row r2.
We observe that the state at step k only depends on the state at step k-1. This allows for space optimization.
We use two 2D arrays, dp[n][n] and current_dp[n][n], to store the results for the previous step (k-1) and the current step (k), respectively.
We iterate k from 1 to 2n-2.
In each iteration, we compute current_dp based on the values in dp.
For each valid state (k, r1, r2), we calculate the maximum cherries from the four possible previous states at k-1: (k-1, r1-1, r2-1), (k-1, r1-1, r2), (k-1, r1, r2-1), and (k-1, r1, r2).
After iterating through all r1 and r2 for a given k, we replace dp with current_dp for the next iteration.
The final answer is max(0, dp[n-1][n-1]) after the loop finishes.

Walkthrough

We build the solution iteratively from the start (0,0) to the end (n-1,n-1). Let dp[r1][r2] be the maximum cherries collected after k steps, with person 1 at row r1 and person 2 at row r2. We iterate through the number of steps k and update the DP table.

1class Solution {2    public int cherryPickup(int[][] grid) {3        int n = grid.length;4        int[][] dp = new int[n][n];5        for (int[] row : dp) {6            java.util.Arrays.fill(row, -1); // Use -1 to indicate unreachable states7        }8        dp[0][0] = grid[0][0];9 10        for (int k = 1; k <= 2 * n - 2; k++) {11            int[][] current_dp = new int[n][n];12            for (int[] row : current_dp) {13                java.util.Arrays.fill(row, -1);14            }15 16            for (int r1 = 0; r1 < n; r1++) {17                for (int r2 = 0; r2 < n; r2++) {18                    int c1 = k - r1;19                    int c2 = k - r2;20 21                    if (c1 < 0 || c1 >= n || c2 < 0 || c2 >= n || grid[r1][c1] == -1 || grid[r2][c2] == -1) {22                        continue;23                    }24 25                    int cherries = grid[r1][c1];26                    if (r1 != r2) { // If they are on different cells, add both cherries27                        cherries += grid[r2][c2];28                    }29 30                    // Find max cherries from previous step (k-1)31                    int prev_max = -1;32                    if (r1 > 0 && r2 > 0 && dp[r1 - 1][r2 - 1] != -1) prev_max = Math.max(prev_max, dp[r1 - 1][r2 - 1]);33                    if (r1 > 0 && dp[r1 - 1][r2] != -1) prev_max = Math.max(prev_max, dp[r1 - 1][r2]);34                    if (r2 > 0 && dp[r1][r2 - 1] != -1) prev_max = Math.max(prev_max, dp[r1][r2 - 1]);35                    if (dp[r1][r2] != -1) prev_max = Math.max(prev_max, dp[r1][r2]);36                    37                    if (prev_max != -1) {38                        current_dp[r1][r2] = cherries + prev_max;39                    }40                }41            }42            dp = current_dp;43        }44 45        return Math.max(0, dp[n - 1][n - 1]);46    }47}

Complexity

Time

O(N^3). The outer loop for `k` runs `O(N)` times, and the two inner loops for `r1` and `r2` run `O(N)` times each, leading to `O(N*N*N)` operations.

Space

O(N^2). We use two N x N arrays to store the DP states for the current and previous steps.

Trade-offs

Pros

Most optimal solution in terms of space complexity.
Avoids recursion overhead, which can lead to slightly better performance in practice.

Cons

The implementation can be more complex to reason about compared to the top-down recursive approach.
The logic for state transitions and boundary conditions needs careful handling.

Solutions

Solution

1class Solution {2public3  int cherryPickup(int[][] grid) {4    int n = grid.length;5    int[][][] dp = new int[n * 2][n][n];6    dp[0][0][0] = grid[0][0];7    for (int k = 1; k < n * 2 - 1; ++k) {8      for (int i1 = 0; i1 < n; ++i1) {9        for (int i2 = 0; i2 < n; ++i2) {10          int j1 = k - i1, j2 = k - i2;11          dp[k][i1][i2] = Integer.MIN_VALUE;12          if (j1 < 0 || j1 >= n || j2 < 0 || j2 >= n || grid[i1][j1] == -1 ||13              grid[i2][j2] == -1) {14            continue;15          }16          int t = grid[i1][j1];17          if (i1 != i2) {18            t += grid[i2][j2];19          }20          for (int x1 = i1 - 1; x1 <= i1; ++x1) {21            for (int x2 = i2 - 1; x2 <= i2; ++x2) {22              if (x1 >= 0 && x2 >= 0) {23                dp[k][i1][i2] = Math.max(dp[k][i1][i2], dp[k - 1][x1][x2] + t);24              }25            }26          }27        }28      }29    }30    return Math.max(0, dp[n * 2 - 2][n - 1][n - 1]);31  }32}

1/** * @param {number[][]} grid * @return {number} */ var cherryPickup = function ( grid ) { const n = grid . length ; let dp = new Array ( n * 2 - 1 ); for ( let k = 0 ; k < dp . length ; ++ k ) { dp [ k ] = new Array ( n ); for ( let i = 0 ; i < n ; ++ i ) { dp [ k ][ i ] = new Array ( n ). fill ( - 1 e9 ); } } dp [ 0 ][ 0 ][ 0 ] = grid [ 0 ][ 0 ]; for ( let k = 1 ; k < n * 2 - 1 ; ++ k ) { for ( let i1 = 0 ; i1 < n ; ++ i1 ) { for ( let i2 = 0 ; i2 < n ; ++ i2 ) { const j1 = k - i1 , j2 = k - i2 ; if ( j1 < 0 || j1 >= n || j2 < 0 || j2 >= n || grid [ i1 ][ j1 ] == - 1 || grid [ i2 ][ j2 ] == - 1 ) { continue ; } let t = grid [ i1 ][ j1 ]; if ( i1 != i2 ) { t += grid [ i2 ][ j2 ]; } for ( let x1 = i1 - 1 ; x1 <= i1 ; ++ x1 ) { for ( let x2 = i2 - 1 ; x2 <= i2 ; ++ x2 ) { if ( x1 >= 0 && x2 >= 0 ) { dp [ k ][ i1 ][ i2 ] = Math . max ( dp [ k ][ i1 ][ i2 ], dp [ k - 1 ][ x1 ][ x2 ] + t ); } } } } } } return Math . max ( 0 , dp [ n * 2 - 2 ][ n - 1 ][ n - 1 ]); };2

1class Solution {2public:3  int cherryPickup(vector<vector<int>> &grid) {4    int n = grid.size();5    vector<vector<vector<int>>> dp(6        n << 1, vector<vector<int>>(n, vector<int>(n, -1e9)));7    dp[0][0][0] = grid[0][0];8    for (int k = 1; k < n * 2 - 1; ++k) {9      for (int i1 = 0; i1 < n; ++i1) {10        for (int i2 = 0; i2 < n; ++i2) {11          int j1 = k - i1, j2 = k - i2;12          if (j1 < 0 || j1 >= n || j2 < 0 || j2 >= n || grid[i1][j1] == -1 ||13              grid[i2][j2] == -1)14            continue;15          int t = grid[i1][j1];16          if (i1 != i2)17            t += grid[i2][j2];18          for (int x1 = i1 - 1; x1 <= i1; ++x1)19            for (int x2 = i2 - 1; x2 <= i2; ++x2)20              if (x1 >= 0 && x2 >= 0)21                dp[k][i1][i2] = max(dp[k][i1][i2], dp[k - 1][x1][x2] + t);22        }23      }24    }25    return max(0, dp[n * 2 - 2][n - 1][n - 1]);26  }27};

1class Solution:2    def cherryPickup(self, grid: List[List[int]]) -> int: n = len(grid) dp = [[[- inf] * n for _ in range(n)] for _ in range((n << 1) - 1)] dp[0][0][0] = grid[0][0] for k in range(1, (n << 1) - 1): for i1 in range(n): for i2 in range(n): j1, j2 = k - i1, k - i2 if (not 0 <= j1 < n or not 0 <= j2 < n or grid[i1][j1] == - 1 or grid[i2][j2] == - 1): continue t = grid[i1][j1] if i1 != i2: t += grid[i2][j2] for x1 in range(i1 - 1, i1 + 1): for x2 in range(i2 - 1, i2 + 1): if x1 >= 0 and x2 >= 0: dp[k][i1][i2] = max(dp[k][i1][i2], dp[k - 1][x1][x2] + t) return max(0, dp[- 1][- 1][- 1])

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem