Find the Maximum Number of Fruits Collected

Hard

#2988Time: O(n^3) There are `n` steps. For each step, we compute an `n x n` DP table. Each cell computation takes O(1) time (a constant 9 lookups). This results in `n * n * n * 9 = O(n^3)` operations.Space: O(n^3) or O(n^2) A naive implementation uses a 3D DP table of size `n x n x n`. This can be optimized to `O(n^2)` because computing the DP values for step `s` only requires the values from step `s-1`. We can use two `n x n` arrays to store the previous and current states.

Patterns

Dynamic Programming

Data structures

Array Matrix

Prompt

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 1^st child (green) moves on the path (0,0) -> (1,1) -> (2,2) -> (3, 3).
The 2^nd child (red) moves on the path (0,3) -> (1,2) -> (2,3) -> (3, 3).
The 3^rd 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 1^st child moves on the path (0,0) -> (1,1).
The 2^nd child moves on the path (0,1) -> (1,1).
The 3^rd 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

Approaches

2 approaches with complexity analysis and trade-offs.

A foundational insight is that the path for the first child (starting at (0,0)) is fixed. This child must make n-1 moves to reach (n-1, n-1). An analysis of its allowed moves ((i+1, j), (i, j+1), (i+1, j+1)) reveals that to cover a distance of n-1 in both row and column indices over n-1 steps, every move must be diagonal ((i+1, j+1)). Thus, child 1's path is fixed along the main diagonal: (0,0) -> (1,1) -> ... -> (n-1, n-1).

With child 1's path determined, the problem reduces to finding the optimal paths for the other two children (C2 and C3) on the grid, avoiding double-counting fruits on the main diagonal. We can model this as a combined dynamic programming problem where the state captures the simultaneous progress of both children.

Let dp[s][c2][r3] be the maximum fruits collected by C2 and C3 after s moves, where C2 is at (s, c2) and C3 is at (r3, s). The state transitions involve checking the 9 possible previous positions of the two children at step s-1.

Algorithm

Determine that child 1's path is fixed along the main diagonal (i,i).Calculate the sum of fruits on this path and conceptually remove them from the grid (e.g., by setting their values to 0 in a copy).Define a DP state dp[s][c2][r3] representing the max fruits for C2 and C3 after s moves, with C2 at (s, c2) and C3 at (r3, s).Initialize the DP table for the base case s=0.Iterate from s=1 to n-1, filling the DP table using the recurrence relation which checks the 9 possible previous states.The result for C2 and C3 is dp[n-1][n-1][n-1]. Add this to the fruits collected by C1.

Walkthrough

Algorithm

Fix Child 1's Path: First, calculate the sum of fruits along the main diagonal, as this path is fixed for child 1. Let's call this c1_fruits. To avoid double counting, we can imagine these fruits are removed from the grid for the other two children.
DP State Definition: Define a 3D DP table, dp[s][c2][r3], to store the maximum fruits collected by child 2 and child 3 after s steps. At step s, child 2 is at row s and some column c2, and child 3 is at column s and some row r3.
Base Case: At s=0, child 2 is at (0, n-1) and child 3 is at (n-1, 0). So, dp[0][n-1][n-1] = fruits[0][n-1] + fruits[n-1][0]. All other dp[0][c2][r3] states are invalid and should be initialized to a very small number (e.g., negative infinity) to indicate they are unreachable.
DP Recurrence: Iterate from s = 1 to n-1. For each possible state (s, c2, r3), calculate dp[s][c2][r3] by considering all valid previous states. A state (s, c2, r3) can be reached from a state (s-1, pc2, pr3) where pc2 is in {c2-1, c2, c2+1} and pr3 is in {r3-1, r3, r3+1}. The value is the maximum over these 9 previous DP values, plus the fruits at the new positions (s, c2) and (r3, s). dp[s][c2][r3] = max(dp[s-1][pc2][pr3]) + fruits[s][c2] + fruits[r3][s] (if (s,c2) != (r3,s)).
Final Result: After n-1 steps, all children must be at (n-1, n-1). So, the maximum fruits collected by C2 and C3 is dp[n-1][n-1][n-1]. The total maximum is this value plus c1_fruits.

Code Snippet

1public long findMaxFruits(int[][] fruits) {2    int n = fruits.length;3    long c1Fruits = 0;4    for (int i = 0; i < n; i++) {5        c1Fruits += fruits[i][i];6        fruits[i][i] = 0; // Mark as collected7    }8 9    long[][] prevDp = new long[n][n];10    for (long[] row : prevDp) Arrays.fill(row, -1);11    prevDp[n - 1][n - 1] = fruits[0][n - 1] + fruits[n - 1][0];12 13    for (int s = 1; s < n; s++) {14        long[][] currDp = new long[n][n];15        for (long[] row : currDp) Arrays.fill(row, -1);16        for (int c2 = 0; c2 < n; c2++) {17            for (int r3 = 0; r3 < n; r3++) {18                long maxPrev = -1;19                for (int dc2 = -1; dc2 <= 1; dc2++) {20                    for (int dr3 = -1; dr3 <= 1; dr3++) {21                        int pc2 = c2 + dc2;22                        int pr3 = r3 + dr3;23                        if (pc2 >= 0 && pc2 < n && pr3 >= 0 && pr3 < n && prevDp[pc2][pr3] != -1) {24                            maxPrev = Math.max(maxPrev, prevDp[pc2][pr3]);25                        }26                    }27                }28                if (maxPrev != -1) {29                    currDp[c2][r3] = maxPrev + fruits[s][c2] + fruits[r3][s];30                }31            }32        }33        prevDp = currDp;34    }35 36    return c1Fruits + prevDp[n - 1][n - 1];37}

Complexity

Time

O(n^3) There are `n` steps. For each step, we compute an `n x n` DP table. Each cell computation takes O(1) time (a constant 9 lookups). This results in `n * n * n * 9 = O(n^3)` operations.

Space

O(n^3) or O(n^2) A naive implementation uses a 3D DP table of size `n x n x n`. This can be optimized to `O(n^2)` because computing the DP values for step `s` only requires the values from step `s-1`. We can use two `n x n` arrays to store the previous and current states.

Trade-offs

Pros

It's a correct formulation that captures the dependencies between the paths of child 2 and child 3.
It's a standard DP approach for pathfinding problems with multiple agents.

Cons

The time complexity of O(n^3) is too high for the given constraints (n <= 1000), though it would pass for smaller n (e.g., n <= 70).
The space complexity is O(n^3), which is also very large. It can be optimized to O(n^2), but this is still substantial.

This approach builds upon the previous one with a critical observation: the paths of child 2 and child 3 are actually independent of each other once child 1's path is accounted for.

Child 2 is always at a position (s, c2) and child 3 is at (r3, s) after s moves. For their paths to intersect, they must be at the same cell (i, j) at the same step s. This would require (s, c2) = (r3, s), which implies r3 = s and c2 = s. The intersection point is (s, s), which lies on the main diagonal.

Since child 1's path is exclusively on the main diagonal, any potential meeting point for child 2 and child 3 is already a point on child 1's path. After we account for the fruits collected by child 1 (by zeroing them out for C2 and C3), there is no remaining fruit value at any potential intersection point for C2 and C3. Therefore, the problem of maximizing their collected fruits decouples into two separate, independent pathfinding problems.

Algorithm

Establish that child 1's path is fixed on the main diagonal.Prove that child 2 and child 3 can only intersect on the main diagonal.Conclude that since fruits on the main diagonal are already collected by child 1, the pathfinding problems for child 2 and child 3 become independent.Calculate child 1's fruit sum. Create a temporary grid with diagonal fruits zeroed out.Run a 2D DP to find the max fruit path for child 2. This takes O(n^2) time.Run a separate 2D DP to find the max fruit path for child 3. This also takes O(n^2) time.Sum the results from the three children to get the final answer.

Walkthrough

Algorithm

Account for Child 1: As before, calculate the sum of fruits on the main diagonal (c1_fruits) and create a temporary copy of the fruits grid where the diagonal elements are set to 0.
Independent DP for Child 2: Find the maximum fruit path for child 2 independently.
- Define dp2[s][c] as the maximum fruits child 2 can collect by reaching cell (s, c) in s moves.
- Base Case: dp2[0][n-1] = fruits_copy[0][n-1].
- Recurrence: For s from 1 to n-1, dp2[s][c] = max(dp2[s-1][c-1], dp2[s-1][c], dp2[s-1][c+1]) + fruits_copy[s][c]. Handle boundary conditions for c.
- The total for child 2 is dp2[n-1][n-1].
Independent DP for Child 3: Similarly, find the maximum fruit path for child 3 independently.
- Define dp3[s][r] as the maximum fruits child 3 can collect by reaching cell (r, s) in s moves.
- Base Case: dp3[0][n-1] = fruits_copy[n-1][0] (Note: C3 starts at (n-1,0)).
- Recurrence: For s from 1 to n-1, dp3[s][r] = max(dp3[s-1][r-1], dp3[s-1][r], dp3[s-1][r+1]) + fruits_copy[r][s]. Handle boundary conditions for r.
- The total for child 3 is dp3[n-1][n-1].
Final Result: The total maximum fruits is the sum of the amounts collected by each child: c1_fruits + dp2[n-1][n-1] + dp3[n-1][n-1].

Code Snippet

1public long findMaxFruits(int[][] fruits) {2    int n = fruits.length;3    long c1Fruits = 0;4    int[][] tempFruits = new int[n][n];5    for (int i = 0; i < n; i++) {6        c1Fruits += fruits[i][i];7        for (int j = 0; j < n; j++) {8            tempFruits[i][j] = fruits[i][j];9        }10        tempFruits[i][i] = 0;11    }12 13    // DP for Child 214    long[][] dp2 = new long[n][n];15    for(long[] row : dp2) Arrays.fill(row, -1);16    dp2[0][n - 1] = tempFruits[0][n - 1];17    for (int s = 1; s < n; s++) {18        for (int c = 0; c < n; c++) {19            long maxPrev = -1;20            if (dp2[s - 1][c] != -1) maxPrev = Math.max(maxPrev, dp2[s - 1][c]);21            if (c > 0 && dp2[s - 1][c - 1] != -1) maxPrev = Math.max(maxPrev, dp2[s - 1][c - 1]);22            if (c < n - 1 && dp2[s - 1][c + 1] != -1) maxPrev = Math.max(maxPrev, dp2[s - 1][c + 1]);23            if (maxPrev != -1) {24                dp2[s][c] = maxPrev + tempFruits[s][c];25            }26        }27    }28    long c2Fruits = dp2[n - 1][n - 1];29 30    // DP for Child 331    long[][] dp3 = new long[n][n];32    for(long[] row : dp3) Arrays.fill(row, -1);33    dp3[0][n - 1] = tempFruits[n - 1][0];34    for (int s = 1; s < n; s++) {35        for (int r = 0; r < n; r++) {36            long maxPrev = -1;37            if (dp3[s - 1][r] != -1) maxPrev = Math.max(maxPrev, dp3[s - 1][r]);38            if (r > 0 && dp3[s - 1][r - 1] != -1) maxPrev = Math.max(maxPrev, dp3[s - 1][r - 1]);39            if (r < n - 1 && dp3[s - 1][r + 1] != -1) maxPrev = Math.max(maxPrev, dp3[s - 1][r + 1]);40            if (maxPrev != -1) {41                dp3[s][r] = maxPrev + tempFruits[r][s];42            }43        }44    }45    long c3Fruits = dp3[n - 1][n - 1];46 47    return c1Fruits + c2Fruits + c3Fruits;48}

Complexity

Time

O(n^2) The algorithm consists of three main parts: calculating C1's sum (O(n)), running DP for C2 (O(n^2)), and running DP for C3 (O(n^2)). The dominant part is the DP, leading to an overall time complexity of O(n^2).

Space

O(n^2) or O(n) Each of the two DPs requires an `n x n` table, so the space is O(n^2). This can be optimized to O(n) for each DP since each step `s` only depends on step `s-1`, reducing the total space complexity to O(n).

Trade-offs

Pros

Highly efficient with O(n^2) time complexity, which is optimal and handles large grid sizes.
The logic is simpler to implement than the coupled DP once the decoupling insight is made.
Space can be optimized to O(n) for each DP, making it memory-efficient as well.

Cons

The core insight that the paths of C2 and C3 are independent is not immediately obvious and requires careful analysis of the movement rules and intersection possibilities.

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