Find the Maximum Number of Fruits Collected solution and explanation
Google
9 more videos on this problem
Find the Maximum Number of Fruits Collected | Recursion | Bottom Up | Leetcode 3363 | DP On GridscodestorywithMIK · 1:09:18 · 11K views
Find the Maximum Number of Fruits Collected | Leetcode 3363 | DPTechdose · 30:02 · 5K views
3363. Find the Maximum Number of Fruits Collected | DP | Memoization | Pattern RecognitionAryan Mittal · 18:42 · 2K views
3363. Find the Maximum Number of Fruits Collected - LeetCode [ Hard ] POTD - 7 August 2025Intuit & Code · 37:22 · 708 views
Daily Leetcode #1955: Aug 07, 2025 - 3363. Find the Maximum Number of Fruits CollectedProgramming Live with Larry · 31:08 · 605 views
Leetcode 3363 🔥 Find the Maximum Number of Fruits Collected | Greedy + DP Optimal Approach Study Placement · 24:43 · 505 views
Find the Maximum Number of Fruits Collected | LeetCode 3363 - Pythonimpoldev · 14:59 · 461 views
3363. Find the Maximum Number of Fruits Collected | Leetcode Daily - PythonLeetcode Daily · 4:56 · 437 views
Leetcode 3363. Find the Maximum Number of Fruits Collected | Dynamic Programming Grid Path in PythonStatLearn Tech · 26:15 · 330 views
C++ DP速解難題leetcode 3363 Find the Maximum Number of Fruits CollectedAn-Wen Deng · 13:16 · 279 views
The problem
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 <= 10000 <= 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.
def maxFruitsDP(fruits):
n = len(fruits)
dp = [[[-1] * n for _ in range(n)] for _ in range(n)]
dp[0][0][0] = fruits[0][0] + fruits[0][n-1] + fruits[n-1][0]
for i in range(n):
for j in range(n):
for k in range(n):
if dp[i][j][k] == -1:
continue
current = dp[i][j][k]
fruits_collected = set()
for child, (di, dj) in enumerate([(1, 1), (1, 0), (0, 1)]):
ni, nj, nk = i + di, j + dj, k + (1 if child == 2 else 0)
if ni < n and nj < n and nk < n:
unique_fruits = sum(fruits[x][y] for x, y in {(ni, nj), (nj, nk), (nk, ni)}) - sum(fruits[x][y] for x, y in fruits_collected)
dp[ni][nj][nk] = max(dp[ni][nj][nk], current + unique_fruits)
fruits_collected.update({(ni, nj), (nj, nk), (nk, ni)})
return dp[-1][-1][-1]
fruits = [[1,2,3,4],[5,6,8,7],[9,10,11,12],[13,14,15,16]]
print(maxFruitsDP(fruits)) # Output should be 100function maxFruitsDP(fruits) {
const n = fruits.length;
const dp = Array.from({ length: n }, () =>
Array.from({ length: n }, () =>
Array(n).fill(-1)));
dp[0][0][0] = fruits[0][0] + fruits[0][n - 1] + fruits[n - 1][0];
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
for (let k = 0; k < n; k++) {
if (dp[i][j][k] === -1) continue;
const current = dp[i][j][k];
const fruitsCollected = new Set();
[[i + 1, j + 1], [i + 1, j], [i, j + 1]].forEach(([x, y], idx) => {
const z = idx === 2 ? k + 1 : k;
if (x < n && y < n && z < n) {
const roomSum = [...new Set([(x * 1000 + y), (y * 1000 + z), (z * 1000 + x)])]
.reduce((acc, val) => acc + fruits[Math.floor(val / 1000)][val % 1000], 0);
const uniqueFruits = roomSum - [...fruitsCollected]
.reduce((acc, val) => acc + fruits[Math.floor(val / 1000)][val % 1000], 0);
dp[x][y][z] = Math.max(dp[x][y][z], current + uniqueFruits);
fruitsCollected.add((x * 1000 + y));
}
});
}
}
}
return dp[n - 1][n - 1][n - 1];
}
const fruits = [[1,2,3,4],[5,6,8,7],[9,10,11,12],[13,14,15,16]];
console.log(maxFruitsDP(fruits)); // Output should be 100This 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.
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.
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.
import java.util.HashMap;
import java.util.Map;
class Solution {
private int dfs(int[][] fruits, int i, int j, int k, int[][][] memo) {
if (i >= fruits.length || j >= fruits[0].length || k >= fruits.length) return 0;
if (memo[i][j][k] != -1) return memo[i][j][k];
int currentFruit = fruits[i][i] + fruits[j][fruits.length - 1 - j] + fruits[fruits.length - 1 - k][k];
int maxFruits = Math.max(dfs(fruits, i + 1, j, k, memo),
Math.max(dfs(fruits, i, j + 1, k, memo), dfs(fruits, i, j, k + 1, memo)));
return memo[i][j][k] = currentFruit + maxFruits;
}
public int maxFruitsDFS(int[][] fruits) {
int n = fruits.length;
int[][][] memo = new int[n][n][n];
for (int[][] layer : memo) {
for (int[] row : layer) {
Arrays.fill(row, -1);
}
}
return dfs(fruits, 0, 0, 0, memo);
}
public static void main(String[] args) {
int[][] fruits = {{1, 2, 3, 4}, {5, 6, 8, 7}, {9, 10, 11, 12}, {13, 14, 15, 16}};
Solution sol = new Solution();
System.out.println(sol.maxFruitsDFS(fruits)); // Output should be 100
}
}#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int dfs(vector<vector<int>> &fruits, int i, int j, int k, vector<vector<vector<int>>> &memo) {
if (i >= fruits.size() || j >= fruits[0].size() || k >= fruits.size()) return 0;
if (memo[i][j][k] != -1) return memo[i][j][k];
int maxFruits = 0;
int currentFruit = fruits[i][i] + fruits[j][fruits.size() - 1 - j] + fruits[fruits.size() - 1 - k][k];
maxFruits = max(maxFruits, dfs(fruits, i + 1, j, k, memo));
maxFruits = max(maxFruits, dfs(fruits, i, j + 1, k, memo));
maxFruits = max(maxFruits, dfs(fruits, i, j, k + 1, memo));
return memo[i][j][k] = currentFruit + maxFruits;
}
int maxFruitsDFS(vector<vector<int>>& fruits) {
int n = fruits.size();
vector<vector<vector<int>>> memo(n, vector<vector<int>>(n, vector<int>(n, -1)));
return dfs(fruits, 0, 0, 0, memo);
}
int main() {
vector<vector<int>> fruits = {{1,2,3,4},{5,6,8,7},{9,10,11,12},{13,14,15,16}};
cout << maxFruitsDFS(fruits) << endl; // Output should be 100
return 0;
}This Java solution features a class-based implementation where a method dfs aids DFS traversal similar to C++, and memoized results are stored using a 3D integer array memo to avoid redundant calculations.
Time Complexity: O(n^3), with caching ensuring each state is computed once.
Space Complexity: O(n^3) storage is dictated by recursion depth and intermediate state tracking.
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.
function maxCollectedFruits(fruits: number[][]): number {
const n = fruits.length;
const inf = 1 << 29;
const f: number[][] = Array.from({ length: n }, () => Array(n).fill(-inf));
f[0][n - 1] = fruits[0][n - 1];
for (let i = 1; i < n; i++) {
for (let j = i + 1; j < n; j++) {
f[i][j] = Math.max(f[i - 1][j], f[i - 1][j - 1]) + fruits[i][j];
if (j + 1 < n) {
f[i][j] = Math.max(f[i][j], f[i - 1][j + 1] + fruits[i][j]);
}
}
}
f[n - 1][0] = fruits[n - 1][0];
for (let j = 1; j < n; j++) {
for (let i = j + 1; i < n; i++) {
f[i][j] = Math.max(f[i][j - 1], f[i - 1][j - 1]) + fruits[i][j];
if (i + 1 < n) {
f[i][j] = Math.max(f[i][j], f[i + 1][j - 1] + fruits[i][j]);
}
}
}
let ans = f[n - 2][n - 1] + f[n - 1][n - 2];
for (let i = 0; i < n; i++) {
ans += fruits[i][i];
}
return ans;
}func maxCollectedFruits(fruits [][]int) int {
n := len(fruits)
const inf = 1 << 29
f := make([][]int, n)
for i := range f {
f[i] = make([]int, n)
for j := range f[i] {
f[i][j] = -inf
}
}
f[0][n-1] = fruits[0][n-1]
for i := 1; i < n; i++ {
for j := i + 1; j < n; j++ {
f[i][j] = max(f[i-1][j], f[i-1][j-1]) + fruits[i][j]
if j+1 < n {
f[i][j] = max(f[i][j], f[i-1][j+1]+fruits[i][j])
}
}
}
f[n-1][0] = fruits[n-1][0]
for j := 1; j < n; j++ {
for i := j + 1; i < n; i++ {
f[i][j] = max(f[i][j-1], f[i-1][j-1]) + fruits[i][j]
if i+1 < n {
f[i][j] = max(f[i][j], f[i+1][j-1]+fruits[i][j])
}
}
}
ans := f[n-2][n-1] + f[n-1][n-2]
for i := 0; i < n; i++ {
ans += fruits[i][i]
}
return ans
}impl Solution {
pub fn max_collected_fruits(fruits: Vec<Vec<i32>>) -> i32 {
let n = fruits.len();
let inf = 1 << 29;
let mut f = vec![vec![-inf; n]; n];
f[0][n - 1] = fruits[0][n - 1];
for i in 1..n {
for j in i + 1..n {
f[i][j] = std::cmp::max(f[i - 1][j], f[i - 1][j - 1]) + fruits[i][j];
if j + 1 < n {
f[i][j] = std::cmp::max(f[i][j], f[i - 1][j + 1] + fruits[i][j]);
}
}
}
f[n - 1][0] = fruits[n - 1][0];
for j in 1..n {
for i in j + 1..n {
f[i][j] = std::cmp::max(f[i][j - 1], f[i - 1][j - 1]) + fruits[i][j];
if i + 1 < n {
f[i][j] = std::cmp::max(f[i][j], f[i + 1][j - 1] + fruits[i][j]);
}
}
}
let mut ans = f[n - 2][n - 1] + f[n - 1][n - 2];
for i in 0..n {
ans += fruits[i][i];
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| 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), with caching ensuring each state is computed once. Space Complexity: O(n^3) storage is dictated by recursion depth and intermediate state tracking. |
| Dynamic Programming | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive DFS with Memoization | O(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 |
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.