Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A route on a line collects a contiguous interval of fruit positions. To cover an interval on both sides of the start, visit the nearer endpoint first, then traverse the full interval; a one-sided interval needs only travel to its far endpoint. Shrinking an interval cannot increase this minimum travel cost.

Approach

Maintain a sliding window over the sorted fruit positions and its total fruit count. Add each new right endpoint. While covering the window costs more than k, remove the left endpoint and advance it. The two-sided cost is the interval width plus the smaller distance from the start to either endpoint; one-sided costs use only the farther distance. Update the maximum valid window total. Positive fruit amounts make retaining the widest feasible window for each right endpoint optimal.

class Solution:
    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:
        n = len(fruits)
        total = 0
        res = 0

        def steps(l, r):
            if fruits[l][0] >= startPos:
                return fruits[r][0] - startPos
            elif fruits[r][0] <= startPos:
                return startPos - fruits[l][0]
            else:
                return min(startPos - fruits[l][0], fruits[r][0] - startPos) + fruits[r][0] - fruits[l][0]

        l = 0
        for r in range(n):
            total += fruits[r][1]

            while l <= r and steps(l, r) > k:
                total -= fruits[l][1]
                l += 1

            res = max(res, total)

        return res

Complexity analysis

Let n = fruits.length. Time: O(n), because each fruit enters and leaves the sliding window at most once. Auxiliary space: O(1).