Cherry Pickup
HardPrompt
You are given an n x n grid representing a field of cherries, each cell is one of three possible integers.
0means the cell is empty, so you can pass through,1means the cell contains a cherry that you can pick up and pass through, or-1means 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 value0or1). - 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.lengthn == grid[i].length1 <= n <= 50grid[i][j]is-1,0, or1.grid[0][0] != -1grid[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 whichc2can be derived asc2 = 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 ofgrid[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 ismax(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.
class Solution { private int[][][] memo; private int[][] grid; private int n; public int cherryPickup(int[][] grid) { this.grid = grid; this.n = grid.length; // Using r1, c1, r2 as state. c2 is derived. this.memo = new int[n][n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // Initialize memo table with -1 to indicate not computed java.util.Arrays.fill(memo[i][j], -1); } } return Math.max(0, solve(0, 0, 0)); } private int solve(int r1, int c1, int r2) { int c2 = r1 + c1 - r2; // Check if paths are valid if (r1 >= n || c1 >= n || r2 >= n || c2 >= n || grid[r1][c1] == -1 || grid[r2][c2] == -1) { return Integer.MIN_VALUE; } // Base case: reached destination if (r1 == n - 1 && c1 == n - 1) { return grid[r1][c1]; } // Check memoization table if (memo[r1][c1][r2] != -1) { return memo[r1][c1][r2]; } // Calculate cherries at current step int cherries = 0; if (r1 == r2 && c1 == c2) { cherries = grid[r1][c1]; } else { cherries = grid[r1][c1] + grid[r2][c2]; } // Explore 4 possible next moves int futureCherries = Math.max( Math.max(solve(r1 + 1, c1, r2 + 1), // P1 down, P2 down solve(r1 + 1, c1, r2)), // P1 down, P2 right Math.max(solve(r1, c1 + 1, r2 + 1), // P1 right, P2 down solve(r1, c1 + 1, r2)) // P1 right, P2 right ); // If no valid future path, current path is also invalid if (futureCherries == Integer.MIN_VALUE) { return memo[r1][c1][r2] = Integer.MIN_VALUE; } // Store and return result return memo[r1][c1][r2] = cherries + futureCherries; }}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.
Solutions
Solution
class Solution {public int cherryPickup(int[][] grid) { int n = grid.length; int[][][] dp = new int[n * 2][n][n]; dp[0][0][0] = grid[0][0]; for (int k = 1; k < n * 2 - 1; ++k) { for (int i1 = 0; i1 < n; ++i1) { for (int i2 = 0; i2 < n; ++i2) { int j1 = k - i1, j2 = k - i2; dp[k][i1][i2] = Integer.MIN_VALUE; if (j1 < 0 || j1 >= n || j2 < 0 || j2 >= n || grid[i1][j1] == -1 || grid[i2][j2] == -1) { continue; } int t = grid[i1][j1]; if (i1 != i2) { t += grid[i2][j2]; } for (int x1 = i1 - 1; x1 <= i1; ++x1) { for (int 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]); }}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.