#1918Time: O(N^2), where N is the number of fruit entries. The nested loops iterate through all O(N^2) possible subarrays. All calculations inside the loops take O(1) time.Space: O(N), where N is the number of fruit entries. This is for storing the prefix sum array.1 company
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 mostk 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 <= 105
fruits[i].length == 2
0 <= startPos, positioni <= 2 * 105
positioni-1 < positioni for any i > 0 (0-indexed)
1 <= amounti <= 104
0 <= k <= 2 * 105
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward approach is to check every possible continuous range of fruits that can be harvested. We can iterate through all possible start and end points of a harvest trip, calculate the cost in steps, and if it's within our budget k, we find the sum of fruits and update our maximum.
Algorithm
Pre-calculate a prefix sum array for the fruit amounts to quickly find the sum of fruits in any given range [i, j].
Initialize a variable maxFruits to 0.
Use nested loops to iterate through every possible continuous subarray of fruits, defined by a start index i and an end index j (0 <= i <= j < n).
For each subarray [i, j], let leftPos = fruits[i][0] and rightPos = fruits[j][0].
Calculate the total steps required to travel from startPos and cover the entire range [leftPos, rightPos].
If the entire range is to the right of startPos (startPos <= leftPos), the cost is rightPos - startPos.
If the entire range is to the left of startPos (rightPos <= startPos), the cost is startPos - leftPos.
If the range spans startPos (leftPos < startPos < rightPos), the cost is the minimum of going left first then right, or right first then left:
If the calculated steps are less than or equal to k, it's a valid trip. Calculate the total fruits in this range [i, j] using the prefix sum array.
Update maxFruits with the maximum value found so far.
After checking all (i, j) pairs, return maxFruits.
Walkthrough
This method exhaustively checks every possible contiguous block of fruits. A block is defined by a starting index i and an ending index j from the fruits array. For each pair (i, j), we determine the minimum number of steps required to start at startPos, visit fruits[i], fruits[j], and all fruits in between.
The cost of a trip depends on the positions of the interval [fruits[i][0], fruits[j][0]] relative to startPos. If the interval is entirely to one side, the cost is simply the distance from startPos to the farthest point. If the interval spans startPos, we must consider two paths: going left first and then crossing over to the right end, or vice-versa. We take the minimum of these two path costs.
To avoid re-calculating the sum of fruits for each range, which would make the complexity O(N^3), we can pre-compute a prefix sum array. This allows us to find the sum of fruits for any range [i, j] in O(1) time. We then compare the fruits collected for each valid trip and keep track of the maximum.
1class Solution {2 public int maxTotalFruits(int[][] fruits, int startPos, int k) {3 int n = fruits.length;4 int[] prefixSum = new int[n + 1];5 for (int i = 0; i < n; i++) {6 prefixSum[i + 1] = prefixSum[i] + fruits[i][1];7 }89 int maxFruits = 0;1011 for (int i = 0; i < n; i++) {12 for (int j = i; j < n; j++) {13 int leftPos = fruits[i][0];14 int rightPos = fruits[j][0];15 int steps = 0;1617 if (rightPos <= startPos) { // Go left only18 steps = startPos - leftPos;19 } else if (leftPos >= startPos) { // Go right only20 steps = rightPos - startPos;21 } else { // Go both ways22 int dist1 = 2 * (startPos - leftPos) + (rightPos - startPos);23 int dist2 = 2 * (rightPos - startPos) + (startPos - leftPos);24 steps = Math.min(dist1, dist2);25 }2627 if (steps <= k) {28 int currentFruits = prefixSum[j + 1] - prefixSum[i];29 maxFruits = Math.max(maxFruits, currentFruits);30 }31 }32 }3334 return maxFruits;35 }36}
Complexity
Time
O(N^2), where N is the number of fruit entries. The nested loops iterate through all O(N^2) possible subarrays. All calculations inside the loops take O(1) time.
Space
O(N), where N is the number of fruit entries. This is for storing the prefix sum array.
Trade-offs
Pros
Simple to understand and implement.
Correctly explores all possible harvesting ranges.
Cons
The time complexity of O(N^2) is too slow for the given constraints (N up to 10^5), and will likely result in a 'Time Limit Exceeded' error on most platforms.
We can improve upon the brute-force approach by optimizing the search for the second endpoint of the harvesting range. Instead of a linear scan for the other end, which leads to an O(N^2) complexity, we can use binary search. For a fixed starting direction and a fixed turning point, the farthest reachable point in the other direction is monotonic, which allows for binary search.
Algorithm
Pre-calculate a prefix sum array for the fruit amounts.
Initialize maxFruits to 0.
The core idea is to fix one end of the journey and find the optimal other end using binary search.
Case 1: Go left first, then optionally right.
Iterate through each fruit fruits[i] to the left of or at startPos as the leftmost point of the journey.
Calculate the distance to go left: distLeft = startPos - fruits[i][0]. If distLeft > k, we can't reach it, so we can stop.
The total steps for a trip that goes left to fruits[i] and then right to fruits[j] is 2 * distLeft + (fruits[j][0] - startPos). This must be <= k.
This gives us the maximum reachable position on the right: rightBound = startPos + k - 2 * distLeft.
Use binary search (e.g., upper_bound) on the fruit positions to find the index j of the rightmost fruit within rightBound.
Calculate the fruits in range [i, j] and update maxFruits.
Case 2: Go right first, then optionally left.
Symmetrically, iterate through each fruit fruits[j] to the right of or at startPos as the rightmost point.
The maximum reachable position on the left is leftBound = startPos - (k - 2 * distRight).
Use binary search (e.g., lower_bound) to find the index i of the leftmost fruit within leftBound.
Calculate fruits in [i, j] and update maxFruits.
Return the overall maxFruits.
Walkthrough
This approach breaks the problem down into two main scenarios: starting by moving left, or starting by moving right.
For the first scenario (move left, then right), we iterate through every possible leftmost fruit fruits[i] that we might visit. For each fruits[i], we calculate the steps needed to reach it (startPos - fruits[i][0]). The cost of the round trip to fruits[i] and back to startPos is 2 * (startPos - fruits[i][0]). The remaining steps, k - 2 * (startPos - fruits[i][0]), can be used to travel right. This determines a maximum reachable position on the right side. Since the fruits array is sorted by position, we can use binary search to efficiently find the rightmost fruit fruits[j] that falls within this reachable boundary. The total fruits for the range [i, j] are then calculated using a prefix sum array.
The second scenario (move right, then left) is handled symmetrically. We iterate through every possible rightmost fruit fruits[j], calculate the remaining steps for a trip to the left, determine the leftmost reachable position, and use binary search to find the corresponding fruits[i].
This method effectively reduces the search for the second endpoint from O(N) to O(log N), leading to an overall improved time complexity.
1import java.util.Arrays;23class Solution {4 public int maxTotalFruits(int[][] fruits, int startPos, int k) {5 int n = fruits.length;6 int[] positions = new int[n];7 int[] prefixSum = new int[n + 1];8 for (int i = 0; i < n; i++) {9 positions[i] = fruits[i][0];10 prefixSum[i + 1] = prefixSum[i] + fruits[i][1];11 }1213 int maxFruits = 0;1415 // Case 1: Go left first, then right16 for (int i = 0; i < n; i++) {17 int leftPos = positions[i];18 if (leftPos > startPos + k) break;19 int distLeft = Math.abs(startPos - leftPos);20 if (distLeft > k) continue;2122 int remaining_k = k - 2 * distLeft;23 if (remaining_k >= 0) {24 int rightBound = startPos + remaining_k;25 int j = findUpperBound(positions, rightBound);26 int currentFruits = prefixSum[j + 1] - prefixSum[i];27 maxFruits = Math.max(maxFruits, currentFruits);28 }29 // Also consider only going left30 if (leftPos <= startPos) {31 int j = findUpperBound(positions, startPos);32 int currentFruits = prefixSum[j + 1] - prefixSum[i];33 maxFruits = Math.max(maxFruits, currentFruits);34 }35 }3637 // Case 2: Go right first, then left38 for (int j = 0; j < n; j++) {39 int rightPos = positions[j];40 if (rightPos < startPos - k) continue;41 int distRight = Math.abs(startPos - rightPos);42 if (distRight > k) break;4344 int remaining_k = k - 2 * distRight;45 if (remaining_k >= 0) {46 int leftBound = startPos - remaining_k;47 int i = findLowerBound(positions, leftBound);48 int currentFruits = prefixSum[j + 1] - prefixSum[i];49 maxFruits = Math.max(maxFruits, currentFruits);50 }51 // Also consider only going right52 if (rightPos >= startPos) {53 int i = findLowerBound(positions, startPos);54 int currentFruits = prefixSum[j + 1] - prefixSum[i];55 maxFruits = Math.max(maxFruits, currentFruits);56 }57 }5859 return maxFruits;60 }6162 // Finds index of last element <= val63 private int findUpperBound(int[] arr, int val) {64 int low = 0, high = arr.length - 1, ans = -1;65 while(low <= high) {66 int mid = low + (high - low) / 2;67 if (arr[mid] <= val) {68 ans = mid;69 low = mid + 1;70 } else {71 high = mid - 1;72 }73 }74 return ans;75 }7677 // Finds index of first element >= val78 private int findLowerBound(int[] arr, int val) {79 int low = 0, high = arr.length - 1, ans = arr.length;80 while(low <= high) {81 int mid = low + (high - low) / 2;82 if (arr[mid] >= val) {83 ans = mid;84 high = mid - 1;85 } else {86 low = mid + 1;87 }88 }89 return ans;90 }91}
Complexity
Time
O(N log N). We iterate through the fruits array once for each case (O(N)), and inside the loop, we perform a binary search (O(log N)).
Space
O(N) for the prefix sum array and positions array.
Trade-offs
Pros
Significantly more efficient than the brute-force approach.
Passes for larger inputs where O(N^2) would fail.
Cons
The logic is more complex than brute force, involving two separate cases and binary searches.
Still not the most optimal solution in terms of time complexity.
The most optimal solution uses the sliding window technique. This approach avoids redundant calculations by intelligently expanding and shrinking a window over the fruits array. The key insight is that as we expand the window to the right, the left boundary of the optimal window will never move backward. This monotonicity allows for a linear time solution.
Algorithm
Initialize a left pointer to 0, maxFruits to 0, and currentSum to 0.
Iterate with a right pointer from 0 to n-1, expanding a window [left, right].
In each iteration, add the fruits at the right pointer to currentSum: currentSum += fruits[right][1].
Calculate the steps required to harvest the fruits in the current window [left, right].
Let leftPos = fruits[left][0] and rightPos = fruits[right][0].
The cost calculation is the same as in the brute-force approach, depending on the window's position relative to startPos.
While the calculated steps > k and left <= right:
The window is too large/costly. Shrink it from the left.
Subtract the fruits at the left pointer from currentSum: currentSum -= fruits[left][1].
Increment the left pointer: left++.
Re-calculate the steps for the new, smaller window.
After the while loop, the window [left, right] is guaranteed to be valid (i.e., steps <= k).
Update maxFruits = max(maxFruits, currentSum).
After the right pointer has traversed the entire array, return maxFruits.
Walkthrough
We can think of the problem as finding the best possible window of fruits [i, j] that maximizes the sum of amounts while respecting the step limit k. This structure is a perfect fit for a sliding window algorithm.
We use two pointers, left and right, to define the current window of fruits being considered. The right pointer iterates through the fruits array from beginning to end, expanding the window one fruit at a time. For each new fruit added, we calculate the cost to harvest all fruits within the current [left, right] window.
If the cost exceeds k, our window is too 'wide' in terms of travel distance. We must shrink the window from the left by incrementing the left pointer until the cost is once again within our budget k. As we shrink the window, we subtract the amount of the fruit at the old left position from our running sum.
Because both the left and right pointers only move forward through the array, each fruit is processed a constant number of times. This results in a highly efficient linear time complexity. We can maintain the sum of fruits within the window with a single variable, updating it as we slide, which gives us constant space complexity.
1class Solution {2 public int maxTotalFruits(int[][] fruits, int startPos, int k) {3 int n = fruits.length;4 int left = 0;5 int maxFruits = 0;6 int currentSum = 0;78 for (int right = 0; right < n; right++) {9 currentSum += fruits[right][1];1011 // Shrink window from the left if it's too costly12 while (left <= right) {13 int leftPos = fruits[left][0];14 int rightPos = fruits[right][0];15 int steps = 0;1617 if (rightPos <= startPos) { // Go left only18 steps = startPos - leftPos;19 } else if (leftPos >= startPos) { // Go right only20 steps = rightPos - startPos;21 } else { // Go both ways22 int dist1 = 2 * (startPos - leftPos) + (rightPos - startPos);23 int dist2 = 2 * (rightPos - startPos) + (startPos - leftPos);24 steps = Math.min(dist1, dist2);25 }2627 if (steps <= k) {28 break; // Window is valid29 }3031 // Window is invalid, shrink from left32 currentSum -= fruits[left][1];33 left++;34 }3536 maxFruits = Math.max(maxFruits, currentSum);37 }3839 return maxFruits;40 }41}
Complexity
Time
O(N), where N is the number of fruit entries. Both the `right` and `left` pointers traverse the array at most once.
Space
O(1), as we only use a few variables to keep track of the window pointers and the current sum.
Trade-offs
Pros
Optimal time complexity of O(N).
Optimal space complexity of O(1) (excluding input storage).
Cons
The logic for the step calculation within the loop can be slightly complex to formulate correctly, with multiple conditions to check.
Solutions
Solution
1class Solution {2public3 int maxTotalFruits(int[][] fruits, int startPos, int k) {4 int ans = 0, s = 0;5 for (int i = 0, j = 0; j < fruits.length; ++j) {6 int pj = fruits[j][0], fj = fruits[j][1];7 s += fj;8 while (i <= j && pj - fruits[i][0] +9 Math.min(Math.abs(startPos - fruits[i][0]),10 Math.abs(startPos - pj)) >11 k) {12 s -= fruits[i++][1];13 }14 ans = Math.max(ans, s);15 }16 return ans;17 }18}
1class Solution {2public:3 int maxTotalFruits(vector<vector<int>> &fruits, int startPos, int k) {4 int ans = 0, s = 0;5 for (int i = 0, j = 0; j < fruits.size(); ++j) {6 int pj = fruits[j][0], fj = fruits[j][1];7 s += fj;8 while (i <= j &&9 pj - fruits[i][0] +10 min(abs(startPos - fruits[i][0]), abs(startPos - pj)) >11 k) {12 s -= fruits[i++][1];13 }14 ans = max(ans, s);15 }16 return ans;17 }18};
1class Solution:2 def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int: ans = i = s = 0 for j, (pj, fj) in enumerate(fruits): s += fj while (i <= j and pj - fruits[i][0] + min(abs(startPos - fruits[i][0]), abs(startPos - fruits[j][0])) > k): s -= fruits[i][1] i += 1 ans = max(ans, s) return ans
Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.
