Cherry Pickup — Solution in Python, Java & C++
Cherry Pickup solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem, asked at Amazon and Google.
Cherry Pickup is a hard coding problem on arrays, dynamic programming and matrix, asked in Amazon, Google, Uber and MathWorks interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Matrix
- Asked at: Amazon, Google, Uber, MathWorks
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An n × n grid holds 0 (empty), 1 (a cherry) or -1 (a thorn you cannot enter).
Walk from (0,0) to (n-1,n-1) moving only right or down, then walk back to (0,0) moving only left or up, picking up every cherry you pass (each cell's cherry is taken at most once). Return the maximum cherries collected, or 0 if the round trip is impossible.
Example 1
Input: grid = [[0,1,-1],[1,0,-1],[1,1,1]]
Output: 5
Explanation: One path down the left and back along the bottom collects five cherries.
Example 2
Input: grid = [[1,1,-1],[1,-1,1],[-1,1,1]]
Output: 0
Explanation: No round trip exists.
Example 3
Input: grid = [[1,1],[1,1]]
Output: 4
Constraints
n == grid.length == grid[i].length1 <= n <= 50grid[i][j] is -1, 0 or 1grid[0][0] and grid[n-1][n-1] are not -1.
Hints for Cherry Pickup
Hint 1
A return trip going up and left is the same as a second forward trip going down and right.
Hint 2
So walk two paths forward simultaneously and never double-count a shared cell.
Hint 3
After
tsteps both walkers are on the anti-diagonalrow + col = t, so one row index each is enough state.
How to solve Cherry Pickup
Reverse the return journey into a second outbound journey, then advance both walkers in lockstep. After t steps each sits on the diagonal row + col = t, so the state is (t, row1, row2) and the column follows.
Approach
dp[r1][r2]is the best total aftertsteps with the walkers on rowsr1andr2.- Advance
t; each walker either kept its row (moved right) or came from the row above (moved down) — four combinations. - Add
grid[r1][c1], plusgrid[r2][c2]only when the walkers are on different rows, so a shared cell is counted once. - Skip any state landing on a thorn; the answer is
max(0, dp[n-1][n-1])at the final step.
Why it works
Two independent one-way trips collect exactly what one round trip does, because reversing a path preserves the cells visited. The lockstep is what makes the 'shared cell' rule checkable: two walkers can only meet when they are on the same diagonal at the same time, which is precisely when r1 == r2. Clamping the final answer at 0 handles the case where no valid round trip exists, which the NEG sentinel propagates.
Complexity
- Time —
O(n³) - Space —
O(n²)
Pitfalls
- Running two independent greedy or DP passes is wrong — the best single path twice may overlap badly.
- Forgetting the
r1 == r2check double-counts a cherry. - Unreachable states must stay at the sentinel and not leak into a maximum.
Reference solution
Python
from typing import List
def cherryPickup(grid: List[List[int]]) -> int:
n = len(grid)
NEG = -10 ** 6
dp = [[NEG] * n for _ in range(n)]
dp[0][0] = grid[0][0]
for t in range(1, 2 * (n - 1) + 1):
ndp = [[NEG] * n for _ in range(n)]
lo, hi = max(0, t - (n - 1)), min(n - 1, t)
for r1 in range(lo, hi + 1):
for r2 in range(lo, hi + 1):
c1, c2 = t - r1, t - r2
if grid[r1][c1] == -1 or grid[r2][c2] == -1:
continue
best = NEG
for p1 in (r1 - 1, r1):
for p2 in (r2 - 1, r2):
if p1 < 0 or p2 < 0:
continue
best = max(best, dp[p1][p2])
if best == NEG:
continue
val = grid[r1][c1]
if r1 != r2:
val += grid[r2][c2]
ndp[r1][r2] = best + val
dp = ndp
return max(0, dp[n - 1][n - 1])Java
public static int cherryPickup(int[][] grid) {
final int NEG = -1000000;
int n = grid.length;
int[][] dp = new int[n][n];
for (int[] row : dp) Arrays.fill(row, NEG);
dp[0][0] = grid[0][0];
for (int t = 1; t <= 2 * (n - 1); t++) {
int[][] ndp = new int[n][n];
for (int[] row : ndp) Arrays.fill(row, NEG);
int lo = Math.max(0, t - (n - 1)), hi = Math.min(n - 1, t);
for (int r1 = lo; r1 <= hi; r1++) {
for (int r2 = lo; r2 <= hi; r2++) {
int c1 = t - r1, c2 = t - r2;
if (grid[r1][c1] == -1 || grid[r2][c2] == -1) continue;
int best = NEG;
for (int p1 = r1 - 1; p1 <= r1; p1++) {
for (int p2 = r2 - 1; p2 <= r2; p2++) {
if (p1 < 0 || p2 < 0) continue;
best = Math.max(best, dp[p1][p2]);
}
}
if (best == NEG) continue;
int val = grid[r1][c1];
if (r1 != r2) val += grid[r2][c2];
ndp[r1][r2] = best + val;
}
}
dp = ndp;
}
return Math.max(0, dp[n - 1][n - 1]);
}C++
int cherryPickup(vector<vector<int>>& grid) {
const int NEG = -1000000;
int n = (int) grid.size();
vector<vector<int>> dp(n, vector<int>(n, NEG));
dp[0][0] = grid[0][0];
for (int t = 1; t <= 2 * (n - 1); t++) {
vector<vector<int>> ndp(n, vector<int>(n, NEG));
int lo = max(0, t - (n - 1)), hi = min(n - 1, t);
for (int r1 = lo; r1 <= hi; r1++) {
for (int r2 = lo; r2 <= hi; r2++) {
int c1 = t - r1, c2 = t - r2;
if (grid[r1][c1] == -1 || grid[r2][c2] == -1) continue;
int best = NEG;
for (int p1 = r1 - 1; p1 <= r1; p1++) {
for (int p2 = r2 - 1; p2 <= r2; p2++) {
if (p1 < 0 || p2 < 0) continue;
best = max(best, dp[p1][p2]);
}
}
if (best == NEG) continue;
int val = grid[r1][c1];
if (r1 != r2) val += grid[r2][c2];
ndp[r1][r2] = best + val;
}
}
dp = ndp;
}
return max(0, dp[n - 1][n - 1]);
}JavaScript
var cherryPickup = function(grid) {
var NEG = -1000000;
var n = grid.length;
var mk = function() {
var m = [];
for (var a = 0; a < n; a++) {
var row = [];
for (var b = 0; b < n; b++) row.push(NEG);
m.push(row);
}
return m;
};
var dp = mk();
dp[0][0] = grid[0][0];
for (var t = 1; t <= 2 * (n - 1); t++) {
var ndp = mk();
var lo = Math.max(0, t - (n - 1)), hi = Math.min(n - 1, t);
for (var r1 = lo; r1 <= hi; r1++) {
for (var r2 = lo; r2 <= hi; r2++) {
var c1 = t - r1, c2 = t - r2;
if (grid[r1][c1] === -1 || grid[r2][c2] === -1) continue;
var best = NEG;
var p1s = [r1 - 1, r1], p2s = [r2 - 1, r2];
for (var a = 0; a < 2; a++) {
for (var b = 0; b < 2; b++) {
var p1 = p1s[a], p2 = p2s[b];
if (p1 < 0 || p2 < 0) continue;
if (dp[p1][p2] > best) best = dp[p1][p2];
}
}
if (best === NEG) continue;
var val = grid[r1][c1];
if (r1 !== r2) val += grid[r2][c2];
ndp[r1][r2] = best + val;
}
}
dp = ndp;
}
return Math.max(0, dp[n - 1][n - 1]);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming