Cherry Pickup II - Practice Coding Problems

Cherry Pickup II - Problem

Imagine you're managing a cherry orchard with two advanced harvesting robots! 🤖🍒

You have a rows × cols grid representing a cherry field where grid[i][j] contains the number of cherries at position (i, j).

The Setup:

🤖 Robot #1 starts at the top-left corner (0, 0)
🤖 Robot #2 starts at the top-right corner (0, cols-1)

Movement Rules:

From cell (i, j), robots can move to: (i+1, j-1), (i+1, j), or (i+1, j+1)
When a robot passes through a cell, it collects all cherries and the cell becomes empty
If both robots visit the same cell, only one robot gets the cherries
Both robots must reach the bottom row

Goal: Find the maximum number of cherries both robots can collect together!

Input & Output

example_1.py — Basic Case

$ Input: grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]

› Output: 24

💡 Note: Robot 1: (0,0)→(1,1)→(2,1)→(3,1) collecting 3+5+5+1=14 cherries. Robot 2: (0,2)→(1,1)→(2,2)→(3,1) but cell (1,1) already visited by Robot 1, so collects 1+0+5+0=6 cherries. Wait, that's wrong! Both robots move simultaneously, so at (1,1) they collect 5 cherries once. Optimal path: Robot1: (0,0)→(1,0)→(2,1)→(3,1) = 3+2+5+1=11. Robot2: (0,2)→(1,1)→(2,2)→(3,1) = 1+5+5+0=11 (but (3,1) shared). Total: 3+2+1+5+5+5+1 = 22. Actually, optimal is 24 with different paths.

example_2.py — Small Grid

$ 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

💡 Note: Robots start at (0,0) and (0,6). They need to collect maximum cherries while moving down. The large 9 in the middle and strategic positioning allows for optimal collection of 28 cherries total.

example_3.py — Edge Case - Single Row

$ Input: grid = [[1,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1]]

› Output: 2

💡 Note: With only one row, Robot 1 starts at position 0 (collects 1 cherry) and Robot 2 starts at position 19 (collects 1 cherry). Total = 2 cherries since they can't move anywhere.

Constraints

rows == grid.length
cols == grid[i].length
2 ≤ rows, cols ≤ 70
0 ≤ grid[i][j] ≤ 100
Both robots must reach the bottom row

Visualization

Tap to expand

Understanding the Visualization

Initialize

Robot 1 at top-left (0,0), Robot 2 at top-right (0,cols-1)

Simultaneous Movement

Both robots move down simultaneously, each with 3 possible directions

Cherry Collection

Collect cherries from visited cells, avoid double-counting when both visit same cell

Dynamic Programming

Use DP to store optimal results for each state (row, col1, col2)

Key Takeaway

🎯 Key Insight: Use 3D DP with state (row, col1, col2) to efficiently compute the maximum cherries collectible by both robots working together, reducing complexity from exponential to polynomial.

Asked in

G Google 45 a Amazon 38 f Facebook 31 ⊞ Microsoft 22

The optimal solution uses 3D Dynamic Programming with memoization. Key insight: since both robots move down simultaneously, we can represent the state as (row, col1, col2) and store the maximum cherries collectible from each state. Time complexity: O(rows × cols²), avoiding the exponential brute force approach.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Recursion	O(3^(2×rows))	O(rows)	Try all possible path combinations for both robots using recursion
3D Dynamic Programming (Optimal)	O(rows × cols²)	O(rows × cols²)	Use memoized DP with state (row, col1, col2) to avoid recomputing subproblems

Brute Force Recursion — Algorithm Steps

Start both robots at their initial positions (0,0) and (0,cols-1)
For each row, try all 9 combinations of moves (3×3)
Recursively calculate cherries for each valid combination
Handle the case where both robots are in same cell
Return maximum cherries among all valid path combinations

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

Both robots start at opposite corners

Try All Moves

Each robot tries 3 possible moves (9 combinations total)

Recursively Explore

Continue exploring all paths until bottom row

Return Maximum

Compare all path combinations and return best result

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int backtrack(int** grid, int row, int col1, int col2, int rows, int cols) {
    // Base case: out of bounds
    if (col1 < 0 || col1 >= cols || col2 < 0 || col2 >= cols) {
        return 0;
    }
    
    // Base case: reached bottom
    if (row == rows - 1) {
        return col1 == col2 ? grid[row][col1] : grid[row][col1] + grid[row][col2];
    }
    
    // Current cherries
    int cherries = grid[row][col1];
    if (col1 != col2) {
        cherries += grid[row][col2];
    }
    
    // Try all 9 combinations
    int maxFuture = 0;
    for (int move1 = -1; move1 <= 1; move1++) {
        for (int move2 = -1; move2 <= 1; move2++) {
            maxFuture = max(maxFuture, 
                           backtrack(grid, row + 1, col1 + move1, col2 + move2, rows, cols));
        }
    }
    
    return cherries + maxFuture;
}

int cherryPickup(int** grid, int rows, int cols) {
    return backtrack(grid, 0, 0, cols - 1, rows, cols);
}

int main() {
    // Example grid setup
    int rows = 4, cols = 3;
    int** grid = (int**)malloc(rows * sizeof(int*));
    for (int i = 0; i < rows; i++) {
        grid[i] = (int*)malloc(cols * sizeof(int));
    }
    
    int data[4][3] = {{3,1,1},{2,5,1},{1,5,5},{2,1,1}};
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            grid[i][j] = data[i][j];
        }
    }
    
    printf("%d\n", cherryPickup(grid, rows, cols));
    
    // Free memory
    for (int i = 0; i < rows; i++) {
        free(grid[i]);
    }
    free(grid);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(3^(2×rows))

Each robot has 3 choices at each of the 'rows' levels, giving 3^(2×rows) combinations

✓ Linear Growth

Space Complexity

O(rows)

Recursion depth equals number of rows in worst case

✓ Linear Space

89.0K Views

Medium Frequency

~25 min Avg. Time

2.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler