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 * 105This 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.
C++
Java
Python
C#
JavaScript
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.
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.
| 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. |
Top K Frequent Elements - Bucket Sort - Leetcode 347 - Python • NeetCode • 665,789 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