Maximum Fruits Harvested After at Most K Steps

hard sliding window prefix sum two pointers

Problem

Fruits sit on an infinite x-axis: fruits[i] = [position, amount], sorted by position. You start at startPos and may walk left and right for at most k total steps (one step = one unit). You collect every fruit at each position you visit. Return the maximum total amount of fruit you can harvest.

The key insight: an optimal route turns at most once, so the visited positions always form one contiguous interval. We slide a window over that interval, keeping it reachable within k steps. Reaching a window [L, R] costs (R − L) + min(|startPos − L|, |startPos − R|) — walk to the nearer end first, turn once, then sweep to the far end.

Inputfruits = [[2,8],[6,3],[8,6]], startPos = 5, k = 4

Output9

Move right to position 6 (3 fruits) then to position 8 (6 fruits): 3 steps, 3 + 6 = 9 fruits. Position 2 is too far left to also reach.

fruits (pos:amount, comma-separated)

startPos

def maxTotalFruits(fruits, startPos, k):
    best = total = 0
    left = 0
    for right in range(len(fruits)):
        total += fruits[right][1]            # add new fruit to window sum
        # shrink while window [left..right] is unreachable in k steps
        while left <= right:
            lp, rp = fruits[left][0], fruits[right][0]
            cost = (rp - lp) + min(abs(startPos - lp),
                                   abs(startPos - rp))
            if cost <= k:
                break
            total -= fruits[left][1]         # drop the left fruit
            left += 1
        best = max(best, total)
    return best

function maxTotalFruits(fruits, startPos, k) {
  let best = 0, total = 0, left = 0;
  for (let right = 0; right < fruits.length; right++) {
    total += fruits[right][1];               // add new fruit to window sum
    // shrink while window [left..right] is unreachable in k steps
    while (left <= right) {
      const lp = fruits[left][0], rp = fruits[right][0];
      const cost = (rp - lp) +
        Math.min(Math.abs(startPos - lp), Math.abs(startPos - rp));
      if (cost <= k) break;
      total -= fruits[left][1];              // drop the left fruit
      left++;
    }
    best = Math.max(best, total);
  }
  return best;
}

int maxTotalFruits(int[][] fruits, int startPos, int k) {
    int best = 0, total = 0, left = 0;
    for (int right = 0; right < fruits.length; right++) {
        total += fruits[right][1];           // add new fruit to window sum
        // shrink while window [left..right] is unreachable in k steps
        while (left <= right) {
            int lp = fruits[left][0], rp = fruits[right][0];
            int cost = (rp - lp) + Math.min(Math.abs(startPos - lp),
                                            Math.abs(startPos - rp));
            if (cost <= k) break;
            total -= fruits[left][1];        // drop the left fruit
            left++;
        }
        best = Math.max(best, total);
    }
    return best;
}

int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) {
    int best = 0, total = 0, left = 0;
    for (int right = 0; right < (int)fruits.size(); right++) {
        total += fruits[right][1];           // add new fruit to window sum
        // shrink while window [left..right] is unreachable in k steps
        while (left <= right) {
            int lp = fruits[left][0], rp = fruits[right][0];
            int cost = (rp - lp) + min(abs(startPos - lp),
                                       abs(startPos - rp));
            if (cost <= k) break;
            total -= fruits[left][1];        // drop the left fruit
            left++;
        }
        best = max(best, total);
    }
    return best;
}

Explanation

Because you can turn around as much as you want, it looks like there are many paths to consider. The hints collapse this: any optimal walk turns at most once. Going left, then right, then left again is never better than the matching single-turn path — the extra back-and-forth wastes steps. So the set of positions you actually harvest is always a contiguous interval on the axis.

For an interval whose leftmost fruit is at L and rightmost at R, the cheapest way to cover it is to walk to the nearer end first, turn once, and sweep to the far end. That costs (R − L) + min(|startPos − L|, |startPos − R|) steps: the span R − L is unavoidable, and the min(...) is the detour to reach the closer endpoint.

Now it is a classic variable-size sliding window over the sorted fruit array. We expand right to include each fruit, adding its amount to a running total (this total is the prefix-sum of the window). Whenever the window's reach-cost exceeds k, we advance left, subtracting dropped fruit, until the window is affordable again.

Every window we keep is reachable within k steps, so its total is a valid harvest. We track the maximum across all windows. Each pointer only moves forward, so the whole scan is linear.

Example: fruits = [[2,8],[6,3],[8,6]], startPos = 5, k = 4. The window {2,6,8} would cost (8−2)+min(3,3)=9 > 4, so position 2 is dropped. The window {6,8} costs (8−6)+min(1,3)=3 ≤ 4 and yields 3+6 = 9 — the answer.

Time: O(n) Space: O(1)