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 * 105In #2106 Maximum Fruits Harvested After at Most K Steps, the challenge is to collect the maximum number of fruits from positions along a number line while taking at most k steps from a starting position. Because fruits are placed at sorted positions, the key is to evaluate ranges that can be reached within the step constraint.
A common strategy combines prefix sums with a sliding window. First, build a prefix sum array of fruit quantities so the total fruits in any interval can be computed quickly. Then use a window over positions and check whether the left and right boundaries are reachable within k steps considering different movement patterns (go left first or right first). If the distance exceeds k, move the window accordingly.
An alternative approach uses binary search with prefix sums to evaluate reachable intervals efficiently. Both strategies exploit sorted positions and constant‑time range queries to keep the algorithm efficient.
The optimized solution typically runs in O(n) or O(n log n) time depending on the method, with O(n) extra space for prefix sums.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sliding Window + Prefix Sum | O(n) | O(n) |
| Binary Search + Prefix Sum | O(n log n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Does an optimal path have very few patterns? For example, could a path that goes left, turns and goes right, then turns again and goes left be any better than a path that simply goes left, turns, and goes right?
The optimal path turns at most once. That is, the optimal path is one of these: to go left only; to go right only; to go left, turn and go right; or to go right, turn and go left.
Moving x steps left then k-x steps right gives you a range of positions that you can reach.
Use prefix sums to get the sum of all fruits for each possible range.
Use a similar strategy for all the paths that go right, then turn and go left.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, problems like this are common in top tech interviews because they test multiple concepts together, including sliding window, prefix sums, and range optimization. It also evaluates a candidate’s ability to reason about movement constraints and interval selection.
Prefix sums allow constant-time calculation of the total fruits between two indices. This makes it efficient to evaluate many possible intervals while adjusting the window or performing binary searches on positions.
The optimal approach typically uses a sliding window combined with prefix sums. Since fruit positions are sorted, a window can represent a reachable interval, and prefix sums allow fast calculation of fruits within that range while checking if the steps needed stay within k.
Arrays are the main structure used, along with a prefix sum array for quick range queries. The sliding window technique over the sorted fruit positions helps maintain valid intervals within the step constraint.