Problem Description
Fruits are available at some positions on an infinite x-axis. You are given a 2D integer array fruits where fruits[i] = [position_i, amount_i] depicts amount_i fruits at the position position_i. fruits is already sorted by position_i in ascending order, and each position_i 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.
Key Insights
- You can move a total of k steps either to the left or right from the start position.
- The positions with fruits are unique and sorted, which allows for efficient searching.
- Harvesting fruits requires balancing the distance traveled and the amount of fruits collected.
- This problem can be approached using a sliding window technique to maximize the fruits harvested within the allowed steps.
Space and Time Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Solution
The solution involves using a sliding window approach. We will maintain two pointers to represent the current range of positions being considered for harvesting fruits. We will iterate through the sorted list of fruit positions, expanding the right pointer as long as we remain within the allowed k steps from the start position. Whenever we cannot include the next position due to the k-step limit, we'll shift the left pointer to reduce the range. Throughout this process, we'll keep track of the maximum fruits harvested.