Cherry Pickup

Hard
888.

Cherry Pickup

Cherry Pickup is a hard coding problem on arrays, dynamic programming and matrix, asked in Amazon, Google, Uber and MathWorks interviews.

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].length
  • 1 <= n <= 50
  • grid[i][j] is -1, 0 or 1
  • grid[0][0] and grid[n-1][n-1] are not -1.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number}
 */
var cherryPickup = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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].length
  • 1 <= n <= 50
  • grid[i][j] is -1, 0 or 1
  • grid[0][0] and grid[n-1][n-1] are not -1.

Hints for Cherry Pickup

  1. Hint 1

    A return trip going up and left is the same as a second forward trip going down and right.

  2. Hint 2

    So walk two paths forward simultaneously and never double-count a shared cell.

  3. Hint 3

    After t steps both walkers are on the anti-diagonal row + 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

  1. dp[r1][r2] is the best total after t steps with the walkers on rows r1 and r2.
  2. Advance t; each walker either kept its row (moved right) or came from the row above (moved down) — four combinations.
  3. Add grid[r1][c1], plus grid[r2][c2] only when the walkers are on different rows, so a shared cell is counted once.
  4. 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 == r2 check 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