Maximum Fruits Harvested After at Most K Steps — Solution
Maximum Fruits Harvested After at Most K Steps solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Maximum Fruits Harvested After at Most K Steps is a hard coding problem on arrays, binary search and prefix sum, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Binary Search, Prefix Sum, Sliding Window
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Fruit trees stand on an infinite number line. fruits[i] = [position, amount] says that amount fruits lie at position; the positions are strictly increasing and unique.
You start at startPos and may take at most k steps, each step moving one unit left or right. Whenever you stand on a position you collect all the fruit there (fruit is collected only once).
Return the maximum total number of fruits you can collect.
Example 1
Input: fruits = [[1,4],[3,2],[7,5],[9,1]], startPos = 4, k = 5
Output: 7
Explanation: Step left to 3 (1 step), then right to 7 (4 steps): 2 + 5 fruits.
Example 2
Input: fruits = [[0,5],[10,5]], startPos = 5, k = 5
Output: 5
Explanation: Either tree is reachable, but not both.
Example 3
Input: fruits = [[2,6],[9,4]], startPos = 5, k = 2
Output: 0
Explanation: Both trees are more than 2 steps away.
Constraints
1 <= fruits.length <= 10^5fruits[i].length == 20 <= startPos, position <= 2 * 10^5position values are strictly increasing1 <= amount <= 10^40 <= k <= 2 * 10^5
Hints for Maximum Fruits Harvested After at Most K Steps
Hint 1
Whatever you do, the positions you visit form one contiguous interval
[L, R]containingstartPos. So the fruit you collect is a contiguous run of trees.Hint 2
Covering
[L, R]fromstakes(R - L) + min(s - L, R - s)steps whenL <= s <= R: go to the nearer end first, then sweep to the other. The same formula works when both ends are on one side if you clampLandRto includes.Hint 3
For a fixed right tree, moving the left tree right never increases the cost, so a sliding window over the trees works: grow on the right, shrink on the left while the cost exceeds
k.
How to solve Maximum Fruits Harvested After at Most K Steps
The visited positions always form an interval around the start, and the cheapest way to cover a run of trees l..r is to reach the nearer end first and then sweep to the far end. That cost is monotone in both ends, so a sliding window over the sorted trees finds the best run.
Approach
- Define
cost(L, R) = (R - L) + min(|s - L|, |R - s|)for tree positionsL <= R— the fewest steps that visit bothLandRstarting froms(it also coversLandRon the same side ofs). - Keep a window of trees
[left, right]and the sum of their fruit. - For each
right, add its fruit; then whileleft <= rightandcost(pos[left], pos[right]) > k, remove treeleftand advanceleft. - Record the window's fruit total if it is the best so far.
Why it works
Any walk of at most k steps visits exactly the integer points of some interval [L, R] containing s; to visit both ends you must reach one end and then cross the whole interval, so the minimum is (R - L) + min(s - L, R - s). When L and R are on the same side of s, the same expression reduces to the distance to the far end. For a fixed right end, raising the left end never raises the cost, and for a fixed left end raising the right end never lowers it — so the left pointer only moves forward and the window visits the best feasible run for every right end.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Going left first and going right first are both candidates — take the minimum, not just one of them.
- Trees entirely on one side of the start are still valid runs; make sure the cost formula handles them (it does with absolute values).
- If no tree is reachable the window empties and the answer stays 0.
Reference solution
Python
from typing import List
def maxTotalFruits(fruits: List[List[int]], startPos: int, k: int) -> int:
def cost(lo: int, hi: int) -> int:
return hi - lo + min(abs(startPos - lo), abs(hi - startPos))
ans = 0
total = 0
left = 0
for right in range(len(fruits)):
total += fruits[right][1]
while left <= right and cost(fruits[left][0], fruits[right][0]) > k:
total -= fruits[left][1]
left += 1
ans = max(ans, total)
return ansJava
public static int maxTotalFruits(int[][] fruits, int startPos, int k) {
int ans = 0, sum = 0, left = 0;
for (int right = 0; right < fruits.length; right++) {
sum += fruits[right][1];
while (left <= right) {
int lo = fruits[left][0], hi = fruits[right][0];
int cost = hi - lo + Math.min(Math.abs(startPos - lo), Math.abs(hi - startPos));
if (cost <= k) break;
sum -= fruits[left][1];
left++;
}
ans = Math.max(ans, sum);
}
return ans;
}C++
int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) {
int ans = 0, sum = 0, left = 0;
for (int right = 0; right < (int) fruits.size(); right++) {
sum += fruits[right][1];
while (left <= right) {
int lo = fruits[left][0], hi = fruits[right][0];
int cost = hi - lo + min(abs(startPos - lo), abs(hi - startPos));
if (cost <= k) break;
sum -= fruits[left][1];
left++;
}
ans = max(ans, sum);
}
return ans;
}JavaScript
var maxTotalFruits = function(fruits, startPos, k) {
var cost = function(lo, hi) {
return hi - lo + Math.min(Math.abs(startPos - lo), Math.abs(hi - startPos));
};
var ans = 0, sum = 0, left = 0;
for (var right = 0; right < fruits.length; right++) {
sum += fruits[right][1];
while (left <= right && cost(fruits[left][0], fruits[right][0]) > k) {
sum -= fruits[left][1];
left++;
}
if (sum > ans) ans = sum;
}
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Binary Search