LeetCode 3363 - Find the Maximum Number of Fruits Collected

LeetCode Problem 3363

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Matrix

Solution

Problem Understanding

This problem asks us to maximize the total number of fruits collected by three children traversing a square grid of rooms, each with a certain number of fruits. The grid has dimensions n x n, and the fruits are given in a 2D array fruits[i][j]. The three children start at fixed corners: (0,0), (0,n-1), and (n-1,0). Each child has specific movement rules that limit them to certain directions per step, and all children must reach the destination (n-1,n-1) in exactly n-1 moves.

The main challenge is that if multiple children occupy the same room simultaneously, only one can collect the fruits. Therefore, we cannot simply sum independent paths; we must consider the interaction between the three paths to avoid double counting.

The input guarantees 2 <= n <= 1000 and 0 <= fruits[i][j] <= 1000. This size indicates that naive brute-force approaches exploring all possible paths are computationally infeasible, as the number of possible path combinations grows exponentially with n.

Edge cases include very small grids (n=2), grids with all zero fruits, and grids where multiple children could overlap at high-value rooms. Proper handling ensures that we do not double-count fruits and that the algorithm gracefully handles the minimum allowed grid size.

Approaches

The brute-force approach would enumerate every possible path for each child while tracking overlaps, summing the fruits for each combination, and selecting the maximum. This is correct in principle because it explores all possibilities, but the number of possible paths is exponential in n, specifically O(3^(n-1) * 3^(n-1) * 3^(n-1)) for the three children. This is clearly infeasible for n up to 1000.

The key observation that enables an efficient solution is dynamic programming with memoization. We notice that each child's next move depends only on its current position, and the sum of positions can serve as a unique state identifier. By defining a DP state dp[x1][x2][x3] representing the maximum fruits collected when the first child is at (x1, y1), the second at (x2, y2), and the third at (x3, y3), where y1 = step - x1, y2 = step - x2, y3 = step - x3, we can recursively compute the best score. This allows us to reuse computations of overlapping subproblems efficiently.

Algorithm Walkthrough

1. Define the DP State: Let dp[x1][x2][x3] be the maximum fruits collected when the first child is at (x1, step-x1), the second at (x2, step-x2 + offset1), and the third at (x3, step-x3 + offset2) based on their movement patterns. The exact y coordinates for each child are calculated based on the number of moves made so far.
2. Compute Base Case: If all children are at the final cell (n-1, n-1), return the fruits at that cell.
3. Calculate Current Step Fruits: At any given state, sum the fruits of the cells occupied by the children. If multiple children occupy the same cell, count the fruits only once.
4. Recursively Explore Moves: For each child, enumerate all valid moves according to the rules (child 1: down, right, diagonal; child 2: down, left, diagonal; child 3: right, up-diagonal, etc.) and recursively compute the maximum fruits collected from that state.
5. Memoize the Result: Store the computed maximum for the current state to avoid recomputation.
6. Return Maximum: After exploring all moves for all children from the initial state (0,0,0) (interpreted as their x coordinates), return the maximum number of fruits collected.

Why it works: The DP state captures all relevant information about the positions of the children and the number of fruits collected, ensuring that overlapping subproblems are reused efficiently. The recursion correctly handles the interaction between children by only counting fruits once per cell.

Python Solution

from functools import lru_cache
from typing import List

class Solution:
    def maxCollectedFruits(self, fruits: List[List[int]]) -> int:
        n = len(fruits)
        
        @lru_cache(maxsize=None)
        def dp(x1: int, x2: int, x3: int) -> int:
            y1 = x1
            y2 = n - 1 - x2
            y3 = x3
            if not (0 <= x1 < n and 0 <= y1 < n and 0 <= x2 < n and 0 <= y2 < n and 0 <= x3 < n and 0 <= y3 < n):
                return float('-inf')
            
            fruits_here = fruits[y1][x1]
            if (x2, y2) != (x1, y1):
                fruits_here += fruits[y2][x2]
            if (x3, y3) != (x1, y1) and (x3, y3) != (x2, y2):
                fruits_here += fruits[y3][x3]
            
            if (x1, y1) == (n-1, n-1) and (x2, y2) == (n-1, n-1) and (x3, y3) == (n-1, n-1):
                return fruits_here
            
            max_fruits = float('-inf')
            for nx1 in [x1 + 1, x1]:
                for nx2 in [x2 + 1, x2]:
                    for nx3 in [x3 + 1, x3]:
                        max_fruits = max(max_fruits, dp(nx1, nx2, nx3))
            
            return fruits_here + max_fruits
        
        return dp(0, 0, 0)

The Python implementation defines a memoized recursive function dp(x1, x2, x3) that computes the maximum fruits from the current positions. It carefully calculates each child's y coordinate, sums the fruits with overlap handling, and explores all valid next moves recursively. The memoization ensures repeated states are computed once, reducing time complexity to O(n^3).

Go Solution

func maxCollectedFruits(fruits [][]int) int {
    n := len(fruits)
    memo := make(map[[3]int]int)

    var dp func(x1, x2, x3 int) int
    dp = func(x1, x2, x3 int) int {
        y1 := x1
        y2 := n - 1 - x2
        y3 := x3
        key := [3]int{x1, x2, x3}
        if x1 < 0 || x1 >= n || y1 < 0 || y1 >= n ||
           x2 < 0 || x2 >= n || y2 < 0 || y2 >= n ||
           x3 < 0 || x3 >= n || y3 < 0 || y3 >= n {
            return -1 << 30
        }
        if val, ok := memo[key]; ok {
            return val
        }

        fruitsHere := fruits[y1][x1]
        if x2 != x1 || y2 != y1 {
            fruitsHere += fruits[y2][x2]
        }
        if (x3 != x1 || y3 != y1) && (x3 != x2 || y3 != y2) {
            fruitsHere += fruits[y3][x3]
        }

        if x1 == n-1 && y1 == n-1 && x2 == n-1 && y2 == n-1 && x3 == n-1 && y3 == n-1 {
            memo[key] = fruitsHere
            return fruitsHere
        }

        maxFruits := -1 << 30
        for _, nx1 := range []int{x1, x1 + 1} {
            for _, nx2 := range []int{x2, x2 + 1} {
                for _, nx3 := range []int{x3, x3 + 1} {
                    maxFruits = max(maxFruits, dp(nx1, nx2, nx3))
                }
            }
        }
        memo[key] = fruitsHere + maxFruits
        return memo[key]
    }

    return dp(0, 0, 0)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

The Go solution mirrors the Python approach, using a map for memoization keyed by the children’s positions. It handles index bounds carefully, uses integer constants for negative infinity, and defines a helper max function.

Worked Examples

Example 1: `fruits = [[1,2,3,4],[5,6,8,7],[9,10,11