#2106

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Maximum Fruits Harvested After at Most K Steps

Compute the maximum fruits collectable on an infinite line by moving at most k steps from a start position efficiently.

array binary search sliding window prefix sum

Problem Statement

You are on an infinite x-axis with fruits available at certain positions. Each fruit location is represented as fruits[i] = [positioni, amounti], indicating amounti fruits at positioni. The fruits array is sorted by position in ascending order and all positions are unique.

Starting at startPos, you can move left or right, using one step per unit, with a maximum of k steps allowed. At each position you reach, you collect all fruits present. Return the maximum total number of fruits you can collect without exceeding k steps.

Examples

Example 1

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

Output: 9

The optimal way is to:

Move right to position 6 and harvest 3 fruits
Move right to position 8 and harvest 6 fruits You moved 3 steps and harvested 3 + 6 = 9 fruits in total.

Example 2

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

Output: 14

You can move at most k = 4 steps, so you cannot reach position 0 nor 10. The optimal way is to:

Harvest the 7 fruits at the starting position 5
Move left to position 4 and harvest 1 fruit
Move right to position 6 and harvest 2 fruits
Move right to position 7 and harvest 4 fruits You moved 1 + 3 = 4 steps and harvested 7 + 1 + 2 + 4 = 14 fruits in total.

Example 3

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

Output: 0

You can move at most k = 2 steps and cannot reach any position with fruits.

Constraints

1 <= fruits.length <= 105
fruits[i].length == 2
0 <= startPos, positioni <= 2 * 105
positioni-1 0 (0-indexed)
1 <= amounti <= 104
0 <= k <= 2 * 105

Solution Approach

Binary Search Over Reachable Ranges

Use binary search to find the leftmost and rightmost positions you can reach within k steps. Consider both scenarios: moving left then right, or moving right then left, to ensure all optimal paths are checked.

Sliding Window to Sum Fruits

Once ranges are determined, apply a sliding window over the sorted fruit positions to sum amounts efficiently. Update the maximum collected total whenever a valid window within k steps is found.

Prefix Sum Optimization

Precompute prefix sums of fruit amounts to quickly calculate totals for any interval. This avoids repeated summation and ensures O(n) time complexity when combined with sliding window checks.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Time complexity is O(n) due to scanning the fruits array once with sliding window and prefix sums. Space complexity is O(1) since only indices and totals are tracked, no additional arrays are required.

What Interviewers Usually Probe

Focus on binary search to efficiently identify valid movement intervals.
Watch for off-by-one errors when combining left-right movements within k steps.
Consider prefix sums to avoid recomputing interval sums repeatedly.

Common Pitfalls or Variants

Common pitfalls

Forgetting that optimal paths may involve turning once; don't assume always moving in a single direction.
Exceeding k steps when summing intervals due to miscalculating distance between positions.
Recomputing fruit sums for every interval instead of using prefix sums, which slows the solution.

Follow-up variants

Change the movement cost per step or allow diagonal moves along the x-axis.
Fruits can regenerate after harvesting, requiring multiple passes over positions.
Positions may not be sorted, requiring initial sorting before sliding window application.

FAQ

What is the main strategy to solve Maximum Fruits Harvested After at Most K Steps?

Use binary search to find reachable intervals combined with sliding window and prefix sums to efficiently compute maximum harvest totals.

Can moving left then right yield more fruits than only moving in one direction?

Yes, optimal paths often involve moving one way, turning, and collecting additional fruits without exceeding k steps.

Is sorting the fruits array necessary?

Yes, sorting ensures the sliding window and prefix sum techniques work correctly to evaluate all valid intervals.

How do prefix sums improve performance in this problem?

Prefix sums allow instant calculation of total fruits in any interval, avoiding repeated summation and reducing time complexity to O(n).

What common errors should be avoided?

Avoid exceeding k steps when summing intervals, ignoring the turn in path, or recomputing sums inefficiently instead of using prefix sums.

terminal

Solution

Solution 1: Two Pointers

Let's assume the movement range is $[l, r]$ and the starting position is $\textit{startPos}$. We need to calculate the minimum number of steps required. Based on the position of $\textit{startPos}$, we can divide this into three cases:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:
        ans = i = s = 0
        for j, (pj, fj) in enumerate(fruits):
            s += fj
            while (
                i <= j
                and pj
                - fruits[i][0]
                + min(abs(startPos - fruits[i][0]), abs(startPos - fruits[j][0]))
                > k
            ):
                s -= fruits[i][1]
                i += 1
            ans = max(ans, s)
        return ans

Continue Practicing

#2271 maximum white tiles covered by a carpet #2302 count subarrays with score less than k #1838 frequency of the most frequent element