Skip to main content
Talentd

Find the Maximum Number of Fruits Collected - Solution & Explanation

HardArrayDynamic ProgrammingMatrix24 min readAsked at: Google, Bloomberg
Practice this problem

Problem Statement

There is a game dungeon comprised of n x n rooms arranged in a grid.

You are given a 2D array fruits of size n x n, where fruits[i][j] represents the number of fruits in the room (i, j). Three children will play in the game dungeon, with initial positions at the corner rooms (0, 0), (0, n - 1), and (n - 1, 0).

The children will make exactly n - 1 moves according to the following rules to reach the room (n - 1, n - 1):

  • The child starting from (0, 0) must move from their current room (i, j) to one of the rooms (i + 1, j + 1), (i + 1, j), and (i, j + 1) if the target room exists.
  • The child starting from (0, n - 1) must move from their current room (i, j) to one of the rooms (i + 1, j - 1), (i + 1, j), and (i + 1, j + 1) if the target room exists.
  • The child starting from (n - 1, 0) must move from their current room (i, j) to one of the rooms (i - 1, j + 1), (i, j + 1), and (i + 1, j + 1) if the target room exists.

When a child enters a room, they will collect all the fruits there. If two or more children enter the same room, only one child will collect the fruits, and the room will be emptied after they leave.

Return the maximum number of fruits the children can collect from the dungeon.

 

Example 1:

Input: fruits = [[1,2,3,4],[5,6,8,7],[9,10,11,12],[13,14,15,16]]

Output: 100

Explanation:

In this example:

  • The 1st child (green) moves on the path (0,0) -> (1,1) -> (2,2) -> (3, 3).
  • The 2nd child (red) moves on the path (0,3) -> (1,2) -> (2,3) -> (3, 3).
  • The 3rd child (blue) moves on the path (3,0) -> (3,1) -> (3,2) -> (3, 3).

In total they collect 1 + 6 + 11 + 16 + 4 + 8 + 12 + 13 + 14 + 15 = 100 fruits.

Example 2:

Input: fruits = [[1,1],[1,1]]

Output: 4

Explanation:

In this example:

  • The 1st child moves on the path (0,0) -> (1,1).
  • The 2nd child moves on the path (0,1) -> (1,1).
  • The 3rd child moves on the path (1,0) -> (1,1).

In total they collect 1 + 1 + 1 + 1 = 4 fruits.

 

Constraints:

  • 2 <= n == fruits.length == fruits[i].length <= 1000
  • 0 <= fruits[i][j] <= 1000

Approach Overview

Problem Overview: You are given a matrix where each cell contains a certain number of fruits. Multiple collectors move through the grid simultaneously and gather fruits along their paths. When two collectors land on the same cell, the fruit should only be counted once. The goal is to compute the maximum total fruits that can be collected following the allowed movements.

Approach 1: Recursive DFS with Memoization (Time: O(m * n^2), Space: O(m * n^2))

This approach models the problem as a recursive search where the state represents the row index and the column positions of the collectors. At each step, both collectors move to the next row with possible column shifts (left, stay, right). The recursive function explores all combinations of moves and collects fruits from the current cells. A memoization table caches results for states like (row, col1, col2) so the same subproblem is not recomputed. This drastically reduces exponential branching to polynomial complexity. DFS with memoization is intuitive when you first reason about the transitions and want a clear top‑down formulation.

Approach 2: Dynamic Programming with Three-Dimensional DP Array (Time: O(m * n^2), Space: O(m * n^2))

The optimal approach converts the recursive idea into bottom‑up dynamic programming. Define dp[row][c1][c2] as the maximum fruits collected when both collectors are on row row at columns c1 and c2. For every state, iterate through the nine possible column transitions for the next row (each collector can move left, stay, or right). Add fruits from the current cells, making sure not to double count when c1 == c2. The DP table is filled row by row until the last row is processed. This eliminates recursion overhead and gives a predictable iteration pattern, which performs well in practice for large grids.

Both approaches rely on the same insight: the future result depends only on the current row and the column positions of both collectors. That makes the problem a classic multi‑agent grid DP similar to problems in Dynamic Programming on a Matrix. The DP state captures both positions simultaneously, which is why a three‑dimensional structure is required.

Recommended for interviews: The three‑dimensional DP solution is what interviewers usually expect. Start by describing the recursive state and transitions, then convert it to a bottom‑up DP table. Mentioning the memoized DFS first shows you understand the problem decomposition, while presenting the iterative DP demonstrates strong command of Array and grid dynamic programming techniques.

Approach 1: Dynamic Programming with Three-dimensional DP Array

This approach utilizes a three-dimensional dynamic programming array to store results. We consider a state dp[i][j][k] where:

  • i and j represent the row indices the first two children have reached respectively.
  • k represents the current row index for the third child.

Due to rule-specific movements and considering conflicts (i.e., only one child can collect the fruits from a room at a time), this DP array allows tracking of the optimal number of fruits collected in different scenarios, and eventually handles dimensional overlap by ensuring each cell sum is added only once when concurrent visits happen.

This Python solution defines a function maxFruitsDP which initializes a 3D DP array with all values set to -1 (indicating non-computed states). Starting from the initial state at (0,0,0) reflecting the starting positions of the children, the recursive state transition builds on previously computed maximum fruits, while managing overlaps through a set for unique fruit rooms.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n^3) as each of the three indices i, j, and k can vary independently across n states.

Space Complexity: O(n^3) because the DP state uses a 3D array for storing intermediary results.

Try this approach in the editor →

Approach 2: Recursive DFS with Memoization

This method involves a depth-first recursive search of possible moves, leveraging memoization to store previously computed results for unique (i, j, k) states. It starts each child from their respective initial positions. It attempts all paths valid per child movement rules and combines reachable paths, while strategically caching results to prevent redundant computations.

Here, a recursive function dfs is defined that performs the depth-first search, exploring all valid transition states for the children concurrently, keeping track of fruits using memoization states in a 3D vector. The memo array is initially filled with -1 to represent unvisited states.

Code

C++Java

C++

Java

Complexity

Time Complexity: O(n^3) due to caching in memoization, preventing redundant traversals through previously solved states.

Space Complexity: O(n^3) for memoization storage, slightly alleviated by recursive stack space use.

Try this approach in the editor →

Approach 3: Dynamic Programming

According to the problem description, for the child starting from (0, 0) to reach (n - 1, n - 1) in exactly n - 1 steps, they can only move through the rooms on the main diagonal (i, i), where i = 0, 1, ldots, n - 1. The child starting from (0, n - 1) can only move through rooms above the main diagonal, while the child starting from (n - 1, 0) can only move through rooms below the main diagonal. This means that except for reaching the destination at (n - 1, n - 1), no other rooms will be visited by multiple children.

We can use dynamic programming to calculate the number of fruits that the children starting from (0, n - 1) and (n - 1, 0) can collect when reaching (i, j). Define f[i][j] as the number of fruits a child can collect when reaching (i, j).

For the child starting from (0, n - 1), the state transition equation is:

$ f[i][j] = max(f[i - 1][j], f[i - 1][j - 1], f[i - 1][j + 1]) + fruits[i][j]

Note that f[i - 1][j + 1] is only valid when j + 1 < n.

For the child starting from (n - 1, 0), the state transition equation is:

f[i][j] = max(f[i][j - 1], f[i - 1][j - 1], f[i + 1][j - 1]) + fruits[i][j]

Similarly, f[i + 1][j - 1] is only valid when i + 1 < n.

Finally, the answer is sum_{i=0}^{n-1} fruits[i][i] + f[n-2][n-1] + f[n-1][n-2], which is the sum of fruits on the main diagonal plus the fruits that the two children can collect when reaching (n - 2, n - 1) and (n - 1, n - 2).

The time complexity is O(n^2), and the space complexity is O(n^2), where n$ is the side length of the room grid.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming with Three-dimensional DP Array

Time Complexity: O(n^3) as each of the three indices i, j, and k can vary independently across n states.

Space Complexity: O(n^3) because the DP state uses a 3D array for storing intermediary results.

Recursive DFS with Memoization

Time Complexity: O(n^3) due to caching in memoization, preventing redundant traversals through previously solved states.

Space Complexity: O(n^3) for memoization storage, slightly alleviated by recursive stack space use.

Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive DFS with MemoizationO(m * n^2)O(m * n^2)Good for understanding the state transitions and building the solution top‑down
3D Dynamic Programming (Bottom‑Up)O(m * n^2)O(m * n^2)Best practical solution with iterative DP and no recursion overhead

Video Solution

Find the Maximum Number of Fruits Collected | Recursion | Bottom Up | Leetcode 3363 | DP On Grids • codestorywithMIK • 11,121 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find the Maximum Number of Fruits Collected easy or hard?
Find the Maximum Number of Fruits Collected is categorized as a Hard problem because it requires designing a multi‑dimensional DP state. The challenge comes from tracking two simultaneous positions, avoiding double counting, and handling multiple movement transitions efficiently.
Find the Maximum Number of Fruits Collected Python/Java solution
Python and Java implementations typically use a 3D DP array or recursion with memoization. The algorithm iterates through rows and evaluates all column combinations for the two collectors while exploring nine possible movement transitions. Both implementations achieve O(m * n^2) time complexity.
How to solve Find the Maximum Number of Fruits Collected in O(n)?
An O(n) solution is not feasible because the algorithm must consider pairs of column positions for two collectors across rows. The optimal approach instead uses O(m * n^2) time dynamic programming. Each DP state represents the positions of both collectors on a given row and computes the best achievable result for the remaining grid.
What is the best approach for Find the Maximum Number of Fruits Collected?
The best approach uses dynamic programming with a three‑dimensional DP state dp[row][c1][c2]. It tracks the row and the column positions of both collectors simultaneously. Each state explores the nine possible movement combinations to the next row and accumulates fruits without double counting. This runs in O(m * n^2) time and O(m * n^2) space.
Is Find the Maximum Number of Fruits Collected asked at Google/Amazon/Meta?
Grid dynamic programming problems with multiple agents frequently appear in interviews at companies like Amazon, Google, and Meta. Variants of this problem are similar to well‑known interview questions such as Cherry Pickup II, which tests multi‑state DP design and careful handling of overlapping positions.
What data structure is used in Find the Maximum Number of Fruits Collected?
The core data structure is a three‑dimensional dynamic programming array or a memoization map keyed by (row, col1, col2). This structure stores the maximum fruits collectible from a specific configuration of the two collectors. Arrays and matrix traversal logic are also used to iterate through valid movements.
What is the time complexity of Find the Maximum Number of Fruits Collected?
The optimal solution runs in O(m * n^2) time where m is the number of rows and n is the number of columns. For every row, the algorithm evaluates all pairs of column positions for the two collectors and checks up to nine transition combinations. Space complexity is also O(m * n^2) due to the DP table or memoization cache.

Ready to solve this problem?

Practice Find the Maximum Number of Fruits Collected with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays