LeetCode 2106 - Maximum Fruits Harvested After at Most K Steps

LeetCode Problem 2106

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Sliding Window, Prefix Sum

Solution

Problem Understanding

In this problem, we are given several fruit piles placed on an infinite one dimensional number line. Each pile is represented by a position and the number of fruits available at that position. The input array fruits is already sorted by position, and every position is unique.

You start at position startPos, and you may walk either left or right along the x-axis. Moving one unit costs one step, and you may use at most k total steps. Whenever you visit a position containing fruits, you automatically harvest all fruits there.

The goal is to determine the maximum total number of fruits that can be harvested within the step limit.

The important detail is that movement cost depends on the path taken. If you only move in one direction, the cost is simply the distance traveled. However, if you move in both directions, the total distance depends on which side you visit first.

For example:

• Going left first, then right:

• cost = (startPos - left) + (right - left)

• Going right first, then left:

• cost = (right - startPos) + (right - left)

These can be simplified into:

• min(2 * leftDistance + rightDistance, leftDistance + 2 * rightDistance)

where:

• leftDistance = startPos - left
• rightDistance = right - startPos

The constraints are large:

• fruits.length can be up to 100000
• positions can be up to 200000

This immediately tells us that any quadratic solution will be too slow. We need something close to linear time.

Several edge cases are important:

• k = 0, meaning we can only collect fruits at startPos
• all fruits are too far away to reach
• all reachable fruits lie entirely on one side
• the optimal route requires changing direction exactly once
• the starting position itself may contain fruits

The fact that positions are sorted is extremely important because it enables efficient sliding window techniques.

Approaches

Brute Force Approach

A brute force solution would consider every possible interval of fruit positions and determine whether it can be collected within k steps.

Suppose we choose an interval from index i to index j. Since the fruits are sorted, this interval represents collecting every fruit between positions:

• left = fruits[i][0]
• right = fruits[j][0]

We compute the minimum walking cost needed to cover this interval starting from startPos. If the cost is within k, we sum all fruits inside the interval and update the answer.

The issue is that there are O(n^2) possible intervals. Even if prefix sums reduce interval summation to O(1), the total complexity remains O(n^2), which is far too slow for n = 100000.

Optimal Approach

The key observation is that the valid fruit positions form a contiguous interval on the number line.

If we maintain a sliding window [left, right], we can efficiently determine whether all fruits inside that interval can be harvested within k steps.

Because positions are sorted:

• expanding the right boundary only increases travel cost
• if a window becomes invalid, moving the left boundary rightward can restore validity

This monotonic behavior makes a sliding window possible.

We also maintain a running sum of fruits inside the window, allowing us to compute interval totals in constant time.

The only challenge is correctly computing the minimum movement cost for the current interval.

For a window spanning positions:

• L = fruits[left][0]
• R = fruits[right][0]

the minimum required steps are:

min(
    2 * (startPos - L) + (R - startPos),
    (startPos - L) + 2 * (R - startPos)
)

This formula represents:

• go left first, then right
• go right first, then left

We choose the cheaper route.

Since every index enters and leaves the sliding window at most once, the solution runs in linear time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1) or O(n)	Checks every interval explicitly
Optimal	O(n)	O(1)	Sliding window with movement cost calculation

Algorithm Walkthrough

1. Initialize two pointers:

• left = 0
• iterate right from 0 to n - 1

2. Maintain a running sum of fruits inside the current window:

• whenever right expands, add fruits[right][1]
• whenever left shrinks, subtract fruits[left][1]

3. For every window [left, right], compute:

• leftPos = fruits[left][0]
• rightPos = fruits[right][0]

4. Determine the minimum steps required to collect all fruits in the current interval.

There are two possible traversal strategies:

• go left first, then sweep right
• go right first, then sweep left

Compute:

leftDistance = max(0, startPos - leftPos)
rightDistance = max(0, rightPos - startPos)

Then:

stepsNeeded =
    min(
        2 * leftDistance + rightDistance,
        leftDistance + 2 * rightDistance
    )

5. If stepsNeeded > k, the window is invalid.

Shrink the window from the left until it becomes valid again. 6. After obtaining a valid window, update the answer using the current fruit sum. 7. Continue until all positions have been processed.

Why it works

The sliding window works because fruit positions are sorted. Expanding the right boundary can only increase the travel range, never decrease it. Therefore, once a window becomes invalid, moving the left boundary rightward is the only way to restore validity.

The movement formula correctly computes the cheapest way to traverse the interval because any optimal route changes direction at most once. The algorithm checks both possible orders and takes the minimum.

Since every valid solution corresponds to some contiguous interval, and every interval is examined exactly once by the sliding window, the algorithm always finds the optimal answer.

Python Solution

from typing import List

class Solution:
    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:
        left = 0
        current_sum = 0
        best = 0

        for right in range(len(fruits)):
            current_sum += fruits[right][1]

            while left <= right:
                left_pos = fruits[left][0]
                right_pos = fruits[right][0]

                left_distance = max(0, startPos - left_pos)
                right_distance = max(0, right_pos - startPos)

                steps_needed = min(
                    2 * left_distance + right_distance,
                    left_distance + 2 * right_distance
                )

                if steps_needed <= k:
                    break

                current_sum -= fruits[left][1]
                left += 1

            best = max(best, current_sum)

        return best

The implementation uses a classic sliding window structure.

The variable current_sum stores the total fruits inside the current window. As the right pointer expands, we add the newly included fruit amount.

The inner while loop ensures the window remains valid. If the movement cost exceeds k, we repeatedly remove fruit piles from the left side until the interval becomes reachable again.

The movement calculation is the core of the solution. We compute the distances to the leftmost and rightmost positions relative to startPos, then evaluate both possible traversal orders.

Finally, after each valid window is established, we update the global maximum.

Go Solution

package main

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

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func maxTotalFruits(fruits [][]int, startPos int, k int) int {
	left := 0
	currentSum := 0
	best := 0

	for right := 0; right < len(fruits); right++ {
		currentSum += fruits[right][1]

		for left <= right {
			leftPos := fruits[left][0]
			rightPos := fruits[right][0]

			leftDistance := max(0, startPos-leftPos)
			rightDistance := max(0, rightPos-startPos)

			stepsNeeded := min(
				2*leftDistance+rightDistance,
				leftDistance+2*rightDistance,
			)

			if stepsNeeded <= k {
				break
			}

			currentSum -= fruits[left][1]
			left++
		}

		best = max(best, currentSum)
	}

	return best
}

The Go implementation closely mirrors the Python solution.

Because Go does not provide built in min and max helpers for integers, we define small utility functions.

Slices are used naturally for the fruits array, and integer overflow is not a concern because the maximum fruit total remains within Go's standard integer range.

Worked Examples

Example 1

fruits = [[2,8],[6,3],[8,6]]
startPos = 5
k = 4

Window	Positions	Fruit Sum	Steps Needed	Valid
[0,0]	[2]	8	3	Yes
[0,1]	[2,6]	11	5	No
[1,1]	[6]	3	1	Yes
[1,2]	[6,8]	9	3	Yes

Maximum = 9

Example 2

fruits = [[0,9],[4,1],[5,7],[6,2],[7,4],[10,9]]
startPos = 5
k = 4

Window	Positions	Fruit Sum	Steps Needed	Valid
[0,0]	[0]	9	5	No
[1,1]	[4]	1	1	Yes
[1,2]	[4,5]	8	1	Yes
[1,3]	[4,6]	10	2	Yes
[1,4]	[4,7]	14	4	Yes
[1,5]	[4,10]	23	6	No

Maximum = 14

Example 3

fruits = [[0,3],[6,4],[8,5]]
startPos = 3
k = 2

Window	Positions	Fruit Sum	Steps Needed	Valid
[0,0]	[0]	3	3	No
[1,1]	[6]	4	3	No
[2,2]	[8]	5	5	No

No valid interval exists, so the answer is 0.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each pointer moves at most n times
Space	O(1)	Only a few variables are maintained

The sliding window guarantees linear complexity because each fruit pile is added to the window once and removed once. No nested quadratic behavior occurs.

The algorithm uses constant extra memory since it only stores counters, pointers, and sums.

Test Cases

from typing import List

class Solution:
    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:
        left = 0
        current_sum = 0
        best = 0

        for right in range(len(fruits)):
            current_sum += fruits[right][1]

            while left <= right:
                left_pos = fruits[left][0]
                right_pos = fruits[right][0]

                left_distance = max(0, startPos - left_pos)
                right_distance = max(0, right_pos - startPos)

                steps_needed = min(
                    2 * left_distance + right_distance,
                    left_distance + 2 * right_distance
                )

                if steps_needed <= k:
                    break

                current_sum -= fruits[left][1]
                left += 1

            best = max(best, current_sum)

        return best

sol = Solution()

assert sol.maxTotalFruits([[2,8],[6,3],[8,6]], 5, 4) == 9
# basic example with only right movement

assert sol.maxTotalFruits([[0,9],[4,1],[5,7],[6,2],[7,4],[10,9]], 5, 4) == 14
# optimal path changes direction

assert sol.maxTotalFruits([[0,3],[6,4],[8,5]], 3, 2) == 0
# no reachable fruits

assert sol.maxTotalFruits([[5,10]], 5, 0) == 10
# fruits at starting position with zero movement

assert sol.maxTotalFruits([[1,4],[2,5],[3,6]], 10, 2) == 0
# all fruits unreachable

assert sol.maxTotalFruits([[1,2],[4,10],[6,8]], 4, 2) == 18
# start position included

assert sol.maxTotalFruits([[2,5],[8,7]], 5, 3) == 7
# only one side reachable

assert sol.maxTotalFruits([[1,1],[2,2],[3,3],[4,4],[5,5]], 3, 4) == 15
# can collect everything

assert sol.maxTotalFruits([[0,10000]], 0, 0) == 10000
# minimum movement boundary

assert sol.maxTotalFruits([[0,1],[100000,2],[200000,3]], 100000, 100000) == 5
# large coordinate range

Test Summary

Test	Why
Example 1	Validates simple rightward movement
Example 2	Validates turning direction
Example 3	Validates unreachable fruits
Single pile at start	Tests k = 0
All unreachable	Ensures answer can be 0
Start position included	Verifies harvesting at initial location
One side reachable	Tests directional limitation
Collect everything	Tests large valid interval
Boundary movement	Tests zero step behavior
Large coordinates	Ensures coordinate size does not matter

Edge Cases

One important edge case occurs when k = 0. In this situation, the player cannot move at all, so the only fruits that can be harvested are those located exactly at startPos. A careless implementation might still attempt to expand windows or incorrectly count nearby fruits. This solution handles the case naturally because any interval requiring positive movement becomes invalid immediately.

Another important edge case is when all fruits lie entirely outside the reachable range. For example, if every fruit pile is farther than k steps away, the correct answer is 0. The sliding window correctly shrinks invalid intervals until they disappear, ensuring no unreachable fruit is counted.

A more subtle edge case occurs when the optimal solution requires changing direction once. Many incorrect solutions assume movement should only happen in one direction. However, some inputs require moving left first and then right, or vice versa, to maximize the total harvest. The movement formula explicitly evaluates both traversal orders and always chooses the cheaper one.

Another tricky situation is when fruits exist on both sides of startPos, but visiting both extremes exceeds the step budget. The sliding window naturally removes positions from one side until the interval becomes feasible again, ensuring only valid ranges contribute to the answer.