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.
This approach uses two pointers to determine the maximum fruits collected within k steps. By maintaining two pointers for the left and right potential maximum distances, we explore the feasible maximum fruit collection at each step.
The idea is to treat the problem similarly to a sliding window on each side, adjusting the range as we move our starting point. We compare scenarios starting from moving maximum steps to the left and then slowly extend to the right and vice versa, while recalculating the possible amount harvested within the constraints.
The C solution utilizes two pointers (left and right) to explore the maximum fruits collectible within the constraints. The pointers adjust according to the maximum distance you can make in either direction. As each limit is set, the current amount of fruits collected is recalculated, updating the maximum as necessary.
The time complexity of the solution is O(n) due to the single traversal of the fruits list, where n is the number of positions available in the fruits array. The space complexity is O(1) since no extra space is required outside of a few variables.
This approach utilizes prefix sums for efficient range queries, making it possible to quickly calculate harvested fruits over a dynamic range. Here, we first construct a prefix sum array over fruit positions, treating each integral position up to the farthest fruit position as valid. By utilizing this approach, changes in starting or ending points of your allowed k-step window need not recompute every value from scratch, offering optimization through precomputed knowledge.
Such an approach is especially efficient when repeating searches or adjustments of boundaries to explore the surroundings quickly, allowing instantaneous summation of fruits within valid movement ranges.
The Python solution leverages an array of accumulated sums, enabling quick lookup and calculation of the total fruits collected between two indices. The prefix sum array allows us to swiftly change ranges by shifting indices over which the harvested fruits are assessed. Thus, it efficiently tackles repeated sum determinations inherent in moving start or end points, resulting in its robust and rapid computational features. The solution neatly combines prefix sum with traversal logic across potential ranges with proper checks.
Python
This approach presents O(n + m) time complexity, where n is the number of positions traversed (at worst equal to the difference between max and min position) and m the length of the input, while space complexity remains tied at O(n) due to the extra prefix sum array used.
Let's assume the movement range is [l, r] and the starting position is startPos. We need to calculate the minimum number of steps required. Based on the position of startPos, we can divide this into three cases:
startPos leq l, then we move right from startPos to r. The minimum number of steps is r - startPos;startPos geq r, then we move left from startPos to l. The minimum number of steps is startPos - l;l < startPos < r, we can either move left from startPos to l then right to r, or move right from startPos to r then left to l. The minimum number of steps is r - l + min(\lvert startPos - l \rvert, \lvert r - startPos \rvert).All three cases can be unified by the formula r - l + min(\lvert startPos - l \rvert, \lvert r - startPos \rvert).
Suppose we fix the right endpoint r of the interval and move the left endpoint l to the right. Let's see how the minimum number of steps changes:
startPos leq l, as l increases, the minimum number of steps remains unchanged.startPos > l, as l increases, the minimum number of steps decreases.Therefore, as l increases, the minimum number of steps is non-strictly monotonically decreasing. Based on this, we can use the two-pointer approach to find all qualifying maximum intervals, then take the one with the maximum total fruits among all qualifying intervals as the answer.
Specifically, we use two pointers i and j to point to the left and right indices of the interval, initially i = j = 0. We also use a variable s to record the total number of fruits in the interval, initially s = 0.
Each time we include j in the interval, then update s = s + fruits[j][1]. If the minimum number of steps in the current interval fruits[j][0] - fruits[i][0] + min(\lvert startPos - fruits[i][0] \rvert, \lvert startPos - fruits[j][0] \rvert) is greater than k, we move i to the right in a loop until i > j or the minimum number of steps in the interval is less than or equal to k. At this point, we update the answer ans = max(ans, s). Continue moving j until j reaches the end of the array.
Finally, return the answer.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Two-Pointer Approach | The time complexity of the solution is O(n) due to the single traversal of the fruits list, where n is the number of positions available in the fruits array. The space complexity is O(1) since no extra space is required outside of a few variables. |
| Prefix Sum Approach | This approach presents O(n + m) time complexity, where n is the number of positions traversed (at worst equal to the difference between max and min position) and m the length of the input, while space complexity remains tied at O(n) due to the extra prefix sum array used. |
| Two Pointers | — |
| 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. |
Maximum Fruits Harvested After at Most K Steps | Detailed Explanation | Leetcode 2106 | MIK • codestorywithMIK • 11,243 views views
Watch 9 more video solutions →Practice Maximum Fruits Harvested After at Most K Steps with our built-in code editor and test cases.
Practice on FleetCode