Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The child starting at the top-left must increase both coordinates on every move to reach the destination in n - 1 steps, so its path is the main diagonal. The other two children's useful fruit collections lie in the upper and lower triangles. Their routes can be optimized independently without counting diagonal fruit again.

Approach

Add all main-diagonal values. For the top-right child, use a table where a state is the maximum additional fruit collected on reaching an above-diagonal cell. Initialize the top-right cell. Process rows through n - 2; reachable columns start at max(row + 1, n - 1 - row). Each state takes the best of the three allowed predecessor columns in the previous row and adds its own fruit. Every processed cell has a reachable predecessor, whose score is nonnegative, so unused zero-initialized predecessor entries cannot inflate the maximum.

The value at (n - 2, n - 1) is this child's contribution before the shared destination. Transpose the input matrix in place and run the same routine for the bottom-left child, then add both contributions.

Entering the diagonal early forces the remaining route along it, where fruit is already counted. That tail can instead stay one column above the diagonal until the destination, preserving all earlier fruit and gaining only nonnegative values. The symmetric argument holds below the diagonal. Thus restricting the two routes to their respective triangles loses nothing and prevents overlap.

class Solution:
    def maxCollectedFruits(self, fruits: List[List[int]]) -> int:
        n = len(fruits)
        res = sum(fruits[i][i] for i in range(n))

        def dp():
            grid = [[0] * n for _ in range(n)]
            grid[0][n - 1] = fruits[0][n - 1]

            for i in range(1, n - 1):
                for j in range(max(i + 1, n - 1 - i), n):
                    best = grid[i - 1][j]
                    best = max(best, grid[i - 1][j - 1])
                    if j < n - 1:
                        best = max(best, grid[i - 1][j + 1])
                    grid[i][j] = best + fruits[i][j]

            return grid[n - 2][n - 1]

        res += dp()

        for i in range(n):
            for j in range(i):
                fruits[i][j], fruits[j][i] = fruits[j][i], fruits[i][j]

        res += dp()

        return res

Complexity analysis

Let n be the square-grid side length. Time: O(n^2). Auxiliary space: O(n^2) for the DP table.