Cherry Pickup II

Hard
1058.

Cherry Pickup II

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

Two robots collect cherries from a grid. Robot 1 starts at (0, 0) and robot 2 at (0, n-1). From a cell (i, j) a robot moves to (i+1, j-1), (i+1, j) or (i+1, j+1), and both move one row per turn until they reach the bottom row.

A robot collects the cherries in every cell it visits, and a cell is emptied once visited. If both robots land on the same cell, the cherries there are collected only once.

Return the maximum total cherries.

Example 1

Input
grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
Output
24
Explanation
Robot 1 takes the left path and robot 2 the right; they never share a cell.

Example 2

Input
grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
Output
28

Example 3

Input
grid = [[1,1],[1,1]]
Output
4

Constraints

  • rows == grid.length
  • cols == grid[i].length
  • 2 <= rows, cols <= 70
  • 0 <= grid[i][j] <= 100
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 II — Solution in Python, Java & C++

Cherry Pickup II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

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

Problem statement

Two robots collect cherries from a grid. Robot 1 starts at (0, 0) and robot 2 at (0, n-1). From a cell (i, j) a robot moves to (i+1, j-1), (i+1, j) or (i+1, j+1), and both move one row per turn until they reach the bottom row.

A robot collects the cherries in every cell it visits, and a cell is emptied once visited. If both robots land on the same cell, the cherries there are collected only once.

Return the maximum total cherries.

Example 1

Input: grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
Output: 24
Explanation: Robot 1 takes the left path and robot 2 the right; they never share a cell.

Example 2

Input: grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
Output: 28

Example 3

Input: grid = [[1,1],[1,1]]
Output: 4

Constraints

  • rows == grid.length
  • cols == grid[i].length
  • 2 <= rows, cols <= 70
  • 0 <= grid[i][j] <= 100

Hints for Cherry Pickup II

  1. Hint 1

    Both robots move one row per turn, so they are always on the same row — the row is a shared clock.

  2. Hint 2

    That makes the state (row, column of robot 1, column of robot 2).

  3. Hint 3

    Nine column transitions per step: three choices each.

How to solve Cherry Pickup II

Because the robots descend in lockstep, the row is common to both and the state is just the pair of columns. dp[c1][c2] is the best total with the robots at those columns on the current row; each step tries all nine column moves.

Approach

  1. Initialise dp[0][n-1] with the first row's two starting cells (once if n == 1).
  2. For each subsequent row, build next by trying d1, d2 each in {-1, 0, 1}.
  3. The gain is grid[row][n1] + grid[row][n2], or just one of them when n1 == n2.
  4. After the last row, return the best value in the table.

Why it works

Moving both robots simultaneously is what keeps the state to two columns instead of two independent positions in time — the original Cherry Pickup needs a clever reparametrisation to achieve the same thing, but here the problem hands it to you. The n1 == n2 case is the only place the "emptied cell" rule bites, and double-counting there is the classic wrong answer.

Complexity

  • Time — O(rows · cols² · 9)
  • Space — O(cols²)

Pitfalls

  • A shared cell contributes once, not twice.
  • Unreachable column pairs must stay excluded, or they seed impossible paths with 0.
  • The robots may cross over each other; nothing forbids it.

Reference solution

Python

from typing import List

def cherryPickup(grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    NEG = -1
    dp = [[NEG] * n for _ in range(n)]
    dp[0][n - 1] = grid[0][0] if n == 1 else grid[0][0] + grid[0][n - 1]
    for row in range(1, m):
        nxt = [[NEG] * n for _ in range(n)]
        for c1 in range(n):
            for c2 in range(n):
                if dp[c1][c2] == NEG:
                    continue
                for d1 in (-1, 0, 1):
                    for d2 in (-1, 0, 1):
                        n1, n2 = c1 + d1, c2 + d2
                        if not (0 <= n1 < n and 0 <= n2 < n):
                            continue
                        gain = grid[row][n1] if n1 == n2 else grid[row][n1] + grid[row][n2]
                        nxt[n1][n2] = max(nxt[n1][n2], dp[c1][c2] + gain)
        dp = nxt
    return max(0, max(max(r) for r in dp))

Java

public static int cherryPickup(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    final int NEG = -1;
    int[][] dp = new int[n][n];
    for (int[] row : dp) Arrays.fill(row, NEG);
    dp[0][n - 1] = n == 1 ? grid[0][0] : grid[0][0] + grid[0][n - 1];
    for (int row = 1; row < m; row++) {
        int[][] next = new int[n][n];
        for (int[] r : next) Arrays.fill(r, NEG);
        for (int c1 = 0; c1 < n; c1++) {
            for (int c2 = 0; c2 < n; c2++) {
                if (dp[c1][c2] == NEG) continue;
                for (int d1 = -1; d1 <= 1; d1++) {
                    for (int d2 = -1; d2 <= 1; d2++) {
                        int n1 = c1 + d1, n2 = c2 + d2;
                        if (n1 < 0 || n1 >= n || n2 < 0 || n2 >= n) continue;
                        int gain = n1 == n2 ? grid[row][n1] : grid[row][n1] + grid[row][n2];
                        next[n1][n2] = Math.max(next[n1][n2], dp[c1][c2] + gain);
                    }
                }
            }
        }
        dp = next;
    }
    int best = 0;
    for (int c1 = 0; c1 < n; c1++) {
        for (int c2 = 0; c2 < n; c2++) best = Math.max(best, dp[c1][c2]);
    }
    return best;
}

C++

int cherryPickup(vector<vector<int>>& grid) {
    int m = (int) grid.size(), n = (int) grid[0].size();
    const int NEG = -1;
    vector<vector<int>> dp(n, vector<int>(n, NEG));
    dp[0][n - 1] = n == 1 ? grid[0][0] : grid[0][0] + grid[0][n - 1];
    for (int row = 1; row < m; row++) {
        vector<vector<int>> next(n, vector<int>(n, NEG));
        for (int c1 = 0; c1 < n; c1++) {
            for (int c2 = 0; c2 < n; c2++) {
                if (dp[c1][c2] == NEG) continue;
                for (int d1 = -1; d1 <= 1; d1++) {
                    for (int d2 = -1; d2 <= 1; d2++) {
                        int n1 = c1 + d1, n2 = c2 + d2;
                        if (n1 < 0 || n1 >= n || n2 < 0 || n2 >= n) continue;
                        int gain = n1 == n2 ? grid[row][n1] : grid[row][n1] + grid[row][n2];
                        next[n1][n2] = max(next[n1][n2], dp[c1][c2] + gain);
                    }
                }
            }
        }
        dp = next;
    }
    int best = 0;
    for (int c1 = 0; c1 < n; c1++) {
        for (int c2 = 0; c2 < n; c2++) best = max(best, dp[c1][c2]);
    }
    return best;
}

JavaScript

var cherryPickup = function(grid) {
    var m = grid.length, n = grid[0].length, NEG = -1, a, c1, c2;
    var dp = [];
    for (a = 0; a < n; a++) {
        var row0 = [];
        for (c2 = 0; c2 < n; c2++) row0.push(NEG);
        dp.push(row0);
    }
    dp[0][n - 1] = n === 1 ? grid[0][0] : grid[0][0] + grid[0][n - 1];
    for (var row = 1; row < m; row++) {
        var next = [];
        for (a = 0; a < n; a++) {
            var r2 = [];
            for (c2 = 0; c2 < n; c2++) r2.push(NEG);
            next.push(r2);
        }
        for (c1 = 0; c1 < n; c1++) {
            for (c2 = 0; c2 < n; c2++) {
                if (dp[c1][c2] === NEG) continue;
                for (var d1 = -1; d1 <= 1; d1++) {
                    for (var d2 = -1; d2 <= 1; d2++) {
                        var n1 = c1 + d1, n2 = c2 + d2;
                        if (n1 < 0 || n1 >= n || n2 < 0 || n2 >= n) continue;
                        var gain = n1 === n2 ? grid[row][n1] : grid[row][n1] + grid[row][n2];
                        var cand = dp[c1][c2] + gain;
                        if (cand > next[n1][n2]) next[n1][n2] = cand;
                    }
                }
            }
        }
        dp = next;
    }
    var best = 0;
    for (c1 = 0; c1 < n; c1++) {
        for (c2 = 0; c2 < n; c2++) if (dp[c1][c2] > best) best = dp[c1][c2];
    }
    return best;
};

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