Coding

Cherry pickup II

Asked at

Google

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given a n x m 2d integer array called matrix where matrix[i][j] represents the number of cherries you can pick up from the (i, j) cell.Given two robots that can collect cherries, one is located at the top-leftmost (0, 0) cell and the other at the top-rightmost (0, m-1) cell.

Return the** maximum** number of cherries that can be picked by the two robots in total, following these rules:

Robots that are standing on (i, j) cell can only move to cell (i + 1, j - 1), (i + 1, j), or (i + 1, j + 1), if it exists in the matrix.
A robot will pick up all the cherries in a given cell when it passes through that cell.
If both robots come to the same cell at the same time, only one robot takes the cherries.
Both robots must reach the bottom row in matrix.

Input: matrix = [[2, 1, 3], [4, 2, 5], [1, 6, 2], [7, 2, 8]] Output: 37 Explanation: Possible left robot path:- Start at 0th cell (2) -> down (4) -> down-right (6) ->down-left (7) Possible right robot path:- Start at 2nd cell (3) -> down (5) -> down (2) -> down (8)

Input: matrix = [[1, 4, 4, 1], [1, 2, 2, 1], [5, 6, 10, 11], [8, 1, 1, 1]] Output: 32 Explanation: Possible left robot path:- Start at 0th cell (1) -> down-right (2) -> down (6) ->down-left (8) Possible right robot path:- Start at 3rd cell (1) -> down-left (2) -> down-right (11) -> down (1)

Input: matrix = [[1, 2, 3], [5, 4, 6], [4, 4, 1]]

n == number of rows in matrix
m == number of columns in matrix
2 <= n, m <= 70
0 <= matrix[i][j] <= 1000

cpp

class Solution {
public:
    int cherryPickup(vector<vector<int>>& matrix) {

    }
};

java

class Solution {
    public int cherryPickup(int[][] matrix) {

    }
}

python

class Solution:
    def cherryPickup(self, matrix):

javascript

class Solution {
    cherryPickup(matrix) {

    }
}

csharp

public class Solution
{
    public int CherryPickup(int[][] matrix)
    {

    }
}

func cherryPickup(matrix [][]int) int {
    // Your code goes here
}

Stuck? Show a way to structure it+

01State is row r and the two robots' columns c1 and c2.
02Add both cells' cherries, counting once when columns match.
03Try all nine pairs of next-column moves.
04Memoize or bottom-up compute from the final row.

Reference answer

Both robots always move to the next row, so define dp[r][c1][c2] as the maximum cherries collectible from row r onward when they occupy columns c1 and c2. Gain is grid[r][c1] + grid[r][c2], but only once when c1==c2. Each robot can move left, straight, or right, yielding nine next-state combinations; discard out-of-bounds columns. Start at (0,0,n-1) and either memoize DFS or fill from the last row upward. For R rows and C columns, time is O(RC^29) and space O(C^2) with rolling rows. The overlap rule is essential.

Then expect these follow-ups

How would you reconstruct both robots' paths?
Tests: DP reconstruction
How would you reduce bottom-up memory?
Tests: rolling arrays

Hiring now

Google has 52 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Small Business Field Sales Representative
Denver, Colorado
Senior Technical Program Manager, Special Projects
Denver, Colorado; Lakewood, Colorado, United States
OSP Engineering Lead, Technical Operations
Denver, Colorado

Or practice this question first

Next question