Skip to main content

741. Cherry Pickup

hard

Walk from top-left to bottom-right and back, collecting the maximum cherries. Reframed as two simultaneous paths whose state is a 1D column-pair after diagonalization.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You are given an n x n grid representing a field of cherries, each cell is one of three possible integers. 0 means the cell is empty, so you can pass through, 1 means the cell contains a cherry that you can pick up and pass through, or -1 means the cell contains a thorn that blocks your way. Return the maximum number of cherries you can collect by following the rules below: Starting at the position (0, 0) and reaching (n - 1, n - 1) by moving right or down through valid path cells (cells with value 0 or 1). After reaching (n - 1, n - 1), returning to (0, 0) by moving left or up through valid path cells. When passing through a path cell containing a cherry, you pick it up, and the cell becomes an empty cell 0. If there is no valid path between (0, 0) and (n - 1, n - 1), then no cherries can be collected.

Constraints

  • n == grid.length
  • n == grid[i].length
  • 1 <= n <= 50
  • grid[i][j] is -1, 0, or 1.
  • grid[0][0] != -1
  • grid[n - 1][n - 1] != -1

Examples

Example 1

Input
grid = [[0,1,-1],[1,0,-1],[1,1,1]]
Output
5

Explanation: The player started at (0, 0) and went down, down, right, right reaching (2, 2). 4 cherries were picked up during this single trip, and the matrix becomes [[0,1,-1],[0,0,-1],[0,0,0]]. Then, the player went left, up, up, left returning home, picking up one more cherry. The total number of cherries picked up is 5, and this is the maximum possible.

Example 2

Input
grid = [[1,1,-1],[1,-1,1],[-1,1,1]]
Output
0

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Going forward then backward equals two simultaneous forward walkers from (0,0) to (n-1,n-1).

Hint 2

Both walkers move at the same speed: after k steps each is at some (r, k-r). State collapses to (step, c1, c2).

Hint 3

For fixed step k, dp is indexed by the pair of columns — effectively a 1D-over-column-pairs DP rolled forward.

Solution approach

Reveal approach

Reframe: instead of one walker going forward then backward, run two walkers simultaneously forward from (0, 0) to (n-1, n-1). After exactly k steps each walker is on the anti-diagonal r + c = k, so the rows are r1 = k - c1 and r2 = k - c2. The state collapses to (k, c1, c2). Maintain a 2D dp keyed on (c1, c2) for the current step and roll forward step by step. Transition: from step k to k+1 each walker independently moves right or down — four combinations. Block any state where either cell is -1. If the walkers land on the same cell, count its cherry only once. Return max(0, dp at the final step at (n-1, n-1)). O(n^3) time, O(n^2) per step.

Complexity

Time
O(n^3)
Space
O(n^2)

Related patterns

  • dynamic-programming
  • grid-dp

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google
  • Amazon

Practice these live with InterviewChamp.AI

Drill Cherry Pickup and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →