Cherry Pickup II

Hard

#1351Time: O(9^rows). At each row, the function branches into 9 recursive calls. The depth of the recursion is `rows`, leading to an exponential number of calls.Space: O(rows) for the recursion call stack.2 companies

Patterns

Dynamic Programming

Data structures

Array Matrix

Companies

Flipkart Rubrik

Prompt

You are given a rows x cols matrix grid representing a field of cherries where grid[i][j] represents the number of cherries that you can collect from the (i, j) cell.

You have two robots that can collect cherries for you:

Robot #1 is located at the top-left corner (0, 0), and
Robot #2 is located at the top-right corner (0, cols - 1).

Return the maximum number of cherries collection using both robots by following the rules below:

From a cell (i, j), robots can move to cell (i + 1, j - 1), (i + 1, j), or (i + 1, j + 1).
When any robot passes through a cell, It picks up all cherries, and the cell becomes an empty cell.
When both robots stay in the same cell, only one takes the cherries.
Both robots cannot move outside of the grid at any moment.
Both robots should reach the bottom row in grid.

Example 1:

Input: grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
Output: 24
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (3 + 2 + 5 + 2) = 12.
Cherries taken by Robot #2, (1 + 5 + 5 + 1) = 12.
Total of cherries: 12 + 12 = 24.

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
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (1 + 9 + 5 + 2) = 17.
Cherries taken by Robot #2, (1 + 3 + 4 + 3) = 11.
Total of cherries: 17 + 11 = 28.

Constraints:

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly translates the problem's state transitions into a recursive function. The state is defined by the current row and the column positions of the two robots. Since both robots move down one row at a time, they are always in the same row.

Algorithm

Define a recursive function solve(row, col1, col2) that returns the maximum cherries collected from the current row downwards, with robots at (row, col1) and (row, col2).
Base Case: If row is the last row, return the cherries at the robots' positions. If col1 or col2 are out of bounds, return a very small number to signify an invalid path.
Recursive Step: For the current state (row, col1, col2), calculate the cherries collected at this step. Then, explore all 9 possible next positions (col1 + d1, col2 + d2 where d1, d2 are in {-1, 0, 1}) in the next row by making recursive calls.
The result for the current state is the sum of current cherries and the maximum value returned from the 9 recursive calls.
The initial call is solve(0, 0, cols - 1).

Walkthrough

We define a recursive function, say solve(row, col1, col2), which calculates the maximum cherries that can be collected from the current row to the bottom, given robot 1 is at (row, col1) and robot 2 is at (row, col2). The function works as follows:

Base Case: When the robots reach the last row (row == rows - 1), they collect the cherries in their respective cells and the recursion stops. The value returned is grid[row][col1] + grid[row][col2] (or just grid[row][col1] if they are in the same cell).
Recursive Step: For any other row, the function calculates the cherries collected at the current cells. Then, it explores all possible next moves for both robots. Robot 1 can move to col1-1, col1, or col1+1 in the next row, and similarly for robot 2. This gives 3 * 3 = 9 possible combinations of next positions. The function recursively calls itself for each of these 9 combinations and takes the maximum result. This maximum is added to the cherries collected at the current row.
Boundary Checks: The function must handle cases where a robot moves outside the grid boundaries. Such paths are invalid and should return a value that ensures they are not chosen (e.g., a very small negative number).
The initial call to the function is solve(0, 0, cols - 1).

1class Solution {2    public int cherryPickup(int[][] grid) {3        int rows = grid.length;4        int cols = grid[0].length;5        return solve(0, 0, cols - 1, grid);6    }7 8    private int solve(int row, int col1, int col2, int[][] grid) {9        int rows = grid.length;10        int cols = grid[0].length;11 12        // Boundary checks for columns13        if (col1 < 0 || col1 >= cols || col2 < 0 || col2 >= cols) {14            return Integer.MIN_VALUE;15        }16 17        // Cherries at the current step18        int cherries = grid[row][col1];19        if (col1 != col2) {20            cherries += grid[row][col2];21        }22 23        // Base case: last row24        if (row == rows - 1) {25            return cherries;26        }27 28        // Recursive step: explore all 9 possible next moves29        int maxFutureCherries = 0;30        for (int dc1 = -1; dc1 <= 1; dc1++) {31            for (int dc2 = -1; dc2 <= 1; dc2++) {32                maxFutureCherries = Math.max(maxFutureCherries, solve(row + 1, col1 + dc1, col2 + dc2, grid));33            }34        }35 36        return cherries + maxFutureCherries;37    }38}

Complexity

Time

O(9^rows). At each row, the function branches into 9 recursive calls. The depth of the recursion is `rows`, leading to an exponential number of calls.

Space

O(rows) for the recursion call stack.

Trade-offs

Pros

Simple to understand and implement as it directly models the problem statement.

Cons

Extremely inefficient due to a massive number of redundant computations for the same subproblems.
Will result in a 'Time Limit Exceeded' error on any non-trivial input size.

The brute-force recursive approach suffers from re-calculating the same subproblems multiple times. A subproblem is defined by the state (row, col1, col2). We can optimize this by storing the result of each subproblem in a memoization table (a 3D array) the first time it's computed. Subsequent calls for the same state will simply return the stored result.

Algorithm

Create a 3D memoization array memo[rows][cols][cols] and initialize it with a value like -1 to indicate uncomputed states.
Use the same recursive function solve(row, col1, col2) as in the brute-force approach.
At the beginning of the function, check if memo[row][col1][col2] is already computed (i.e., not -1). If so, return the stored value immediately.
If the state is not memoized, compute the result as before.
Before returning the newly computed result, store it in memo[row][col1][col2] to avoid re-computation in the future.

Walkthrough

This approach enhances the brute-force recursion by adding a cache, or memoization table, to store the results of subproblems. This is a top-down dynamic programming technique.

We use a 3D array, memo[rows][cols][cols], to store the results of our recursive function solve(row, col1, col2).
The memo array is initialized with a special value (e.g., null or -1) to indicate that a state has not yet been computed.
Inside the recursive function, before any computation, we check if memo[row][col1][col2] already contains a valid result. If it does, we return it immediately.
If the result is not in the memo table, we compute it as in the brute-force approach.
Before returning the computed result, we store it in memo[row][col1][col2] for future use.
This technique ensures that each unique state (row, col1, col2) is computed only once, dramatically improving performance.

1class Solution {2    public int cherryPickup(int[][] grid) {3        int rows = grid.length;4        int cols = grid[0].length;5        Integer[][][] memo = new Integer[rows][cols][cols];6        return solve(0, 0, cols - 1, grid, memo);7    }8 9    private int solve(int row, int col1, int col2, int[][] grid, Integer[][][] memo) {10        int rows = grid.length;11        int cols = grid[0].length;12 13        if (col1 < 0 || col1 >= cols || col2 < 0 || col2 >= cols) {14            return Integer.MIN_VALUE;15        }16 17        if (memo[row][col1][col2] != null) {18            return memo[row][col1][col2];19        }20 21        int cherries = grid[row][col1];22        if (col1 != col2) {23            cherries += grid[row][col2];24        }25 26        if (row == rows - 1) {27            return cherries;28        }29 30        int maxFutureCherries = 0;31        for (int dc1 = -1; dc1 <= 1; dc1++) {32            for (int dc2 = -1; dc2 <= 1; dc2++) {33                maxFutureCherries = Math.max(maxFutureCherries, solve(row + 1, col1 + dc1, col2 + dc2, grid, memo));34            }35        }36 37        memo[row][col1][col2] = cherries + maxFutureCherries;38        return memo[row][col1][col2];39    }40}

Complexity

Time

O(rows * cols * cols). Each state `(row, col1, col2)` is computed exactly once. The computation for each state involves a constant number of operations (a loop of 9).

Space

O(rows * cols * cols). This is dominated by the space required for the memoization table. The recursion stack depth adds O(rows).

Trade-offs

Pros

Drastically more efficient than brute-force and guaranteed to solve the problem within time limits.
Often more intuitive to write than the bottom-up tabulation approach.

Cons

Uses significant space for the 3D memoization table.
Recursion overhead can make it slightly slower than an equivalent iterative (tabulation) solution.

This is the most efficient approach. It builds the solution iteratively from the bottom up, which avoids recursion overhead. Furthermore, it optimizes the space complexity by recognizing that to compute the maximum cherries for a given row, we only need the results from the immediately following row.

Algorithm

Create a 2D DP array dp[cols][cols].
Initialization: Populate dp with the results for the last row (rows - 1). dp[c1][c2] will be the sum of cherries at (rows-1, c1) and (rows-1, c2).
Iteration: Loop row from rows - 2 down to 0.
- Inside the loop, create a new 2D array current_dp[cols][cols].
- For each state (row, c1, c2), calculate the maximum cherries from the next row by looking up the 9 possible next states in the dp table (which holds values for row + 1).
- current_dp[c1][c2] = (cherries at current cells) + (max value from dp).
- After the inner loops for c1 and c2 are done, replace the old dp table with current_dp (dp = current_dp).
Result: After the main loop finishes, the answer is dp[0][cols - 1].

Walkthrough

This bottom-up DP approach, also known as tabulation, iteratively builds the solution. We can optimize space because the calculation for any row r only depends on the results from row r+1.

We use a 2D table, dp of size cols x cols, to store the maximum cherries that can be collected from a given row to the end.
Initialization: We start by populating dp as if it represents the last row (rows - 1). For each pair of columns (c1, c2), dp[c1][c2] is initialized with grid[rows-1][c1] + grid[rows-1][c2] (or just grid[rows-1][c1] if c1 == c2).
Iteration: We then iterate backward from the second to last row (r = rows - 2) up to the first row (r = 0). In each iteration, we compute a current_dp table for row r. For each pair of columns (c1, c2), we find the maximum possible sum from the next row (r+1) by checking all 9 states reachable from (c1, c2). The values for row r+1 are already stored in our dp table. The result current_dp[c1][c2] is the sum of cherries at (r, c1) and (r, c2) plus this maximum value from the next row.
After computing the current_dp table for row r, we update dp = current_dp to be used for the calculation of the previous row (r-1).
Final Result: After the main loop completes, dp holds the results for row 0. The answer is dp[0][cols - 1], corresponding to the robots' initial positions.

1class Solution {2    public int cherryPickup(int[][] grid) {3        int rows = grid.length;4        int cols = grid[0].length;5 6        int[][] dp = new int[cols][cols];7 8        // Initialize for the last row9        for (int c1 = 0; c1 < cols; c1++) {10            for (int c2 = 0; c2 < cols; c2++) {11                if (c1 == c2) {12                    dp[c1][c2] = grid[rows - 1][c1];13                } else {14                    dp[c1][c2] = grid[rows - 1][c1] + grid[rows - 1][c2];15                }16            }17        }18 19        // Iterate from the second to last row up to the first20        for (int r = rows - 2; r >= 0; r--) {21            int[][] current_dp = new int[cols][cols];22            for (int c1 = 0; c1 < cols; c1++) {23                for (int c2 = 0; c2 < cols; c2++) {24                    int maxNextRow = 0;25                    // Find max cherries from the next row26                    for (int dc1 = -1; dc1 <= 1; dc1++) {27                        for (int dc2 = -1; dc2 <= 1; dc2++) {28                            int nc1 = c1 + dc1;29                            int nc2 = c2 + dc2;30                            if (nc1 >= 0 && nc1 < cols && nc2 >= 0 && nc2 < cols) {31                                maxNextRow = Math.max(maxNextRow, dp[nc1][nc2]);32                            }33                        }34                    }35                    36                    int currentCherries = grid[r][c1];37                    if (c1 != c2) {38                        currentCherries += grid[r][c2];39                    }40                    current_dp[c1][c2] = currentCherries + maxNextRow;41                }42            }43            dp = current_dp;44        }45 46        return dp[0][cols - 1];47    }48}

Complexity

Time

O(rows * cols * cols). We have a loop for rows, and nested loops for `c1`, `c2`, and the 9 possible moves.

Space

O(cols * cols). We only need space for two 2D arrays of size `cols x cols` to store the DP states for the current and next rows.

Trade-offs

Pros

Most efficient in terms of both time and space.
Avoids recursion overhead, which can lead to a slight performance gain.
Uses significantly less memory than non-optimized DP approaches.

Cons

Can be less intuitive to formulate and implement compared to the top-down memoization approach.

Solutions

Solution

1class Solution {2public3  int cherryPickup(int[][] grid) {4    int m = grid.length, n = grid[0].length;5    int[][][] f = new int[m][n][n];6    for (var g : f) {7      for (var h : g) {8        Arrays.fill(h, -1);9      }10    }11    f[0][0][n - 1] = grid[0][0] + grid[0][n - 1];12    for (int i = 1; i < m; ++i) {13      for (int j1 = 0; j1 < n; ++j1) {14        for (int j2 = 0; j2 < n; ++j2) {15          int x = grid[i][j1] + (j1 == j2 ? 0 : grid[i][j2]);16          for (int y1 = j1 - 1; y1 <= j1 + 1; ++y1) {17            for (int y2 = j2 - 1; y2 <= j2 + 1; ++y2) {18              if (y1 >= 0 && y1 < n && y2 >= 0 && y2 < n &&19                  f[i - 1][y1][y2] != -1) {20                f[i][j1][j2] = Math.max(f[i][j1][j2], f[i - 1][y1][y2] + x);21              }22            }23          }24        }25      }26    }27    int ans = 0;28    for (int j1 = 0; j1 < n; ++j1) {29      for (int j2 = 0; j2 < n; ++j2) {30        ans = Math.max(ans, f[m - 1][j1][j2]);31      }32    }33    return ans;34  }35}

1class Solution {2public:3  int cherryPickup(vector<vector<int>> &grid) {4    int m = grid.size(), n = grid[0].size();5    int f[m][n][n];6    memset(f, -1, sizeof(f));7    f[0][0][n - 1] = grid[0][0] + grid[0][n - 1];8    for (int i = 1; i < m; ++i) {9      for (int j1 = 0; j1 < n; ++j1) {10        for (int j2 = 0; j2 < n; ++j2) {11          int x = grid[i][j1] + (j1 == j2 ? 0 : grid[i][j2]);12          for (int y1 = j1 - 1; y1 <= j1 + 1; ++y1) {13            for (int y2 = j2 - 1; y2 <= j2 + 1; ++y2) {14              if (y1 >= 0 && y1 < n && y2 >= 0 && y2 < n &&15                  f[i - 1][y1][y2] != -1) {16                f[i][j1][j2] = max(f[i][j1][j2], f[i - 1][y1][y2] + x);17              }18            }19          }20        }21      }22    }23    int ans = 0;24    for (int j1 = 0; j1 < n; ++j1) {25      for (int j2 = 0; j2 < n; ++j2) {26        ans = max(ans, f[m - 1][j1][j2]);27      }28    }29    return ans;30  }31};

1class Solution:2    def cherryPickup(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) f = [[[- 1] * n for _ in range(n)] for _ in range(m)] f[0][0][n - 1] = grid[0][0] + grid[0][n - 1] for i in range(1, m): for j1 in range(n): for j2 in range(n): x = grid[i][j1] + (0 if j1 == j2 else grid[i][j2]) for y1 in range(j1 - 1, j1 + 2): for y2 in range(j2 - 1, j2 + 2): if 0 <= y1 < n and 0 <= y2 < n and f[i - 1][y1][y2] != - 1: f[i][j1][j2] = max(f[i][j1][j2], f[i - 1][y1][y2] + x) return max(f[- 1][j1][j2] for j1, j2 in product(range(n), range(n)))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  int cherryPickup(int[][] grid) {4    int m = grid.length, n = grid[0].length;5    int[][][] f = new int[m][n][n];6    for (var g : f) {7      for (var h : g) {8        Arrays.fill(h, -1);9      }10    }11    f[0][0][n - 1] = grid[0][0] + grid[0][n - 1];12    for (int i = 1; i < m; ++i) {13      for (int j1 = 0; j1 < n; ++j1) {14        for (int j2 = 0; j2 < n; ++j2) {15          int x = grid[i][j1] + (j1 == j2 ? 0 : grid[i][j2]);16          for (int y1 = j1 - 1; y1 <= j1 + 1; ++y1) {17            for (int y2 = j2 - 1; y2 <= j2 + 1; ++y2) {18              if (y1 >= 0 && y1 < n && y2 >= 0 && y2 < n &&19                  f[i - 1][y1][y2] != -1) {20                f[i][j1][j2] = Math.max(f[i][j1][j2], f[i - 1][y1][y2] + x);21              }22            }23          }24        }25      }26    }27    int ans = 0;28    for (int j1 = 0; j1 < n; ++j1) {29      for (int j2 = 0; j2 < n; ++j2) {30        ans = Math.max(ans, f[m - 1][j1][j2]);31      }32    }33    return ans;34  }35}

1class Solution {2public:3  int cherryPickup(vector<vector<int>> &grid) {4    int m = grid.size(), n = grid[0].size();5    int f[m][n][n];6    memset(f, -1, sizeof(f));7    f[0][0][n - 1] = grid[0][0] + grid[0][n - 1];8    for (int i = 1; i < m; ++i) {9      for (int j1 = 0; j1 < n; ++j1) {10        for (int j2 = 0; j2 < n; ++j2) {11          int x = grid[i][j1] + (j1 == j2 ? 0 : grid[i][j2]);12          for (int y1 = j1 - 1; y1 <= j1 + 1; ++y1) {13            for (int y2 = j2 - 1; y2 <= j2 + 1; ++y2) {14              if (y1 >= 0 && y1 < n && y2 >= 0 && y2 < n &&15                  f[i - 1][y1][y2] != -1) {16                f[i][j1][j2] = max(f[i][j1][j2], f[i - 1][y1][y2] + x);17              }18            }19          }20        }21      }22    }23    int ans = 0;24    for (int j1 = 0; j1 < n; ++j1) {25      for (int j2 = 0; j2 < n; ++j2) {26        ans = max(ans, f[m - 1][j1][j2]);27      }28    }29    return ans;30  }31};

1class Solution:2    def cherryPickup(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) f = [[[- 1] * n for _ in range(n)] for _ in range(m)] f[0][0][n - 1] = grid[0][0] + grid[0][n - 1] for i in range(1, m): for j1 in range(n): for j2 in range(n): x = grid[i][j1] + (0 if j1 == j2 else grid[i][j2]) for y1 in range(j1 - 1, j1 + 2): for y2 in range(j2 - 1, j2 + 2): if 0 <= y1 < n and 0 <= y2 < n and f[i - 1][y1][y2] != - 1: f[i][j1][j2] = max(f[i][j1][j2], f[i - 1][y1][y2] + x) return max(f[- 1][j1][j2] for j1, j2 in product(range(n), range(n)))

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.