Maximum Fruits Harvested After at Most K Steps

Hard
1365.

Maximum Fruits Harvested After at Most K Steps

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.

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^5
  • fruits[i].length == 2
  • 0 <= startPos, position <= 2 * 10^5
  • position values are strictly increasing
  • 1 <= amount <= 10^4
  • 0 <= k <= 2 * 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} fruits
 * @param {number} startPos
 * @param {number} k
 * @return {number}
 */
var maxTotalFruits = function(fruits, startPos, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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^5
  • fruits[i].length == 2
  • 0 <= startPos, position <= 2 * 10^5
  • position values are strictly increasing
  • 1 <= amount <= 10^4
  • 0 <= k <= 2 * 10^5

Hints for Maximum Fruits Harvested After at Most K Steps

  1. Hint 1

    Whatever you do, the positions you visit form one contiguous interval [L, R] containing startPos. So the fruit you collect is a contiguous run of trees.

  2. Hint 2

    Covering [L, R] from s takes (R - L) + min(s - L, R - s) steps when L <= 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 clamp L and R to include s.

  3. 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

  1. Define cost(L, R) = (R - L) + min(|s - L|, |R - s|) for tree positions L <= R — the fewest steps that visit both L and R starting from s (it also covers L and R on the same side of s).
  2. Keep a window of trees [left, right] and the sum of their fruit.
  3. For each right, add its fruit; then while left <= right and cost(pos[left], pos[right]) > k, remove tree left and advance left.
  4. 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 ans

Java

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