Watch 10 video solutions for Maximum Fruits Harvested After at Most K Steps, a hard level problem involving Array, Binary Search, Sliding Window. This walkthrough by codestorywithMIK has 11,243 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Fruits are available at some positions on an infinite x-axis. You are given a 2D integer array fruits where fruits[i] = [positioni, amounti] depicts amounti fruits at the position positioni. fruits is already sorted by positioni in ascending order, and each positioni is unique.
You are also given an integer startPos and an integer k. Initially, you are at the position startPos. From any position, you can either walk to the left or right. It takes one step to move one unit on the x-axis, and you can walk at most k steps in total. For every position you reach, you harvest all the fruits at that position, and the fruits will disappear from that position.
Return the maximum total number of fruits you can harvest.
Example 1:
Input: fruits = [[2,8],[6,3],[8,6]], startPos = 5, k = 4 Output: 9 Explanation: 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 Explanation: 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 Explanation: You can move at most k = 2 steps and cannot reach any position with fruits.
Constraints:
1 <= fruits.length <= 105fruits[i].length == 20 <= startPos, positioni <= 2 * 105positioni-1 < positioni for any i > 0 (0-indexed)1 <= amounti <= 1040 <= k <= 2 * 105Problem Overview: You are given fruit positions on a number line where fruits[i] = [position, amount]. Starting at startPos, you can walk left or right for at most k total steps. The goal is to collect the maximum total fruits from visited positions. Since positions are sorted, the challenge is determining which contiguous range of positions can be visited within the step constraint.
Approach 1: Two-Pointer Sliding Window (O(n) time, O(1) space)
This approach uses a sliding window across the sorted fruit positions. Maintain two pointers left and right representing the current harvestable range. As you expand right, compute the minimum walking distance needed to visit both ends of the window starting from startPos. The key observation: the optimal path either goes left first then right, or right first then left. The distance can be computed using min(2*(startPos-left) + (right-startPos), 2*(right-startPos) + (startPos-left)). If the required steps exceed k, move left forward. Maintain the running fruit sum for the window and update the maximum. This method works efficiently because every position is visited at most twice.
Approach 2: Prefix Sum + Binary Search (O(n log n) time, O(n) space)
Another strategy uses prefix sums combined with binary search. First extract the fruit positions and build a prefix sum array of fruit counts so range sums can be queried in O(1). For each candidate stopping point on one side of startPos, compute how far you can extend in the opposite direction while staying within k steps. Because positions are sorted, binary search quickly finds the farthest valid boundary. The prefix sum array then calculates the fruit total for that segment. While this method is slightly slower than the sliding window, it is conceptually straightforward when thinking in terms of reachable intervals.
Recommended for interviews: The two-pointer sliding window approach is typically expected. It demonstrates understanding of ordered arrays, window expansion/shrinking, and distance optimization on a number line. Discussing the prefix sum + binary search approach still shows strong problem-solving skills, especially when reasoning about reachable ranges and efficient range-sum queries.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer Sliding Window | O(n) | O(1) | Best choice when fruit positions are sorted and you need the optimal linear-time solution. |
| Prefix Sum + Binary Search | O(n log n) | O(n) | Useful when reasoning about reachable ranges and performing fast range-sum queries. |