LeetCode #2106 — HARD

Maximum Fruits Harvested After at Most K Steps

Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.

The Problem

Problem Statement

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.

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 <= 10⁵
fruits[i].length == 2
0 <= startPos, position_i <= 2 * 10⁵
position_i-1 < position_i for any i > 0 (0-indexed)
1 <= amount_i <= 10⁴
0 <= k <= 2 * 10⁵

Step 01

Brute Force Baseline

Problem summary: 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 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.

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Array · Binary Search · Sliding Window

Example 1

[[2,8],[6,3],[8,6]]
5
4

Example 2

[[0,9],[4,1],[5,7],[6,2],[7,4],[10,9]]
5
4

Example 3

[[0,3],[6,4],[8,5]]
3
2

Core Insight

What unlocks the optimal approach

Does an optimal path have very few patterns? For example, could a path that goes left, turns and goes right, then turns again and goes left be any better than a path that simply goes left, turns, and goes right?
The optimal path turns at most once. That is, the optimal path is one of these: to go left only; to go right only; to go left, turn and go right; or to go right, turn and go left.
Moving x steps left then k-x steps right gives you a range of positions that you can reach.
Use prefix sums to get the sum of all fruits for each possible range.
Use a similar strategy for all the paths that go right, then turn and go left.

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Largest constraint values

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #2106: Maximum Fruits Harvested After at Most K Steps
class Solution {
    public int maxTotalFruits(int[][] fruits, int startPos, int k) {
        int ans = 0, s = 0;
        for (int i = 0, j = 0; j < fruits.length; ++j) {
            int pj = fruits[j][0], fj = fruits[j][1];
            s += fj;
            while (i <= j
                && pj - fruits[i][0]
                        + Math.min(Math.abs(startPos - fruits[i][0]), Math.abs(startPos - pj))
                    > k) {
                s -= fruits[i++][1];
            }
            ans = Math.max(ans, s);
        }
        return ans;
    }
}

// Accepted solution for LeetCode #2106: Maximum Fruits Harvested After at Most K Steps
func maxTotalFruits(fruits [][]int, startPos int, k int) (ans int) {
	var s, i int
	for j, f := range fruits {
		s += f[1]
		for i <= j && f[0]-fruits[i][0]+min(abs(startPos-fruits[i][0]), abs(startPos-f[0])) > k {
			s -= fruits[i][1]
			i += 1
		}
		ans = max(ans, s)
	}
	return
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

# Accepted solution for LeetCode #2106: Maximum Fruits Harvested After at Most K Steps
class Solution:
    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

// Accepted solution for LeetCode #2106: Maximum Fruits Harvested After at Most K Steps
impl Solution {
    pub fn max_total_fruits(fruits: Vec<Vec<i32>>, start_pos: i32, k: i32) -> i32 {
        let mut ans = 0;
        let mut s = 0;
        let mut i = 0;
        for j in 0..fruits.len() {
            let pj = fruits[j][0];
            let fj = fruits[j][1];
            s += fj;
            while i <= j
                && pj - fruits[i][0]
                    + std::cmp::min((start_pos - fruits[i][0]).abs(), (start_pos - pj).abs())
                    > k
            {
                s -= fruits[i][1];
                i += 1;
            }
            ans = ans.max(s)
        }
        ans
    }
}

// Accepted solution for LeetCode #2106: Maximum Fruits Harvested After at Most K Steps
function maxTotalFruits(fruits: number[][], startPos: number, k: number): number {
    let ans = 0;
    let s = 0;
    for (let i = 0, j = 0; j < fruits.length; ++j) {
        const [pj, fj] = fruits[j];
        s += fj;
        while (
            i <= j &&
            pj -
                fruits[i][0] +
                Math.min(Math.abs(startPos - fruits[i][0]), Math.abs(startPos - pj)) >
                k
        ) {
            s -= fruits[i++][1];
        }
        ans = Math.max(ans, s);
    }
    return ans;
}

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(log n)

Space

O(1)

Approach Breakdown

LINEAR SCAN

O(n) time

O(1) space

Check every element from left to right until we find the target or exhaust the array. Each comparison is O(1), and we may visit all n elements, giving O(n). No extra space needed.

BINARY SEARCH

O(log n) time

O(1) space

Each comparison eliminates half the remaining search space. After k comparisons, the space is n/2ᵏ. We stop when the space is 1, so k = log₂ n. No extra memory needed — just two pointers (lo, hi).

Shortcut: Halving the input each step → O(log n). Works on any monotonic condition, not just sorted arrays.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Off-by-one on range boundaries

Wrong move: Loop endpoints miss first/last candidate.

Usually fails on: Fails on minimal arrays and exact-boundary answers.

Fix: Re-derive loops from inclusive/exclusive ranges before coding.

Boundary update without `+1` / `-1`

Wrong move: Setting `lo = mid` or `hi = mid` can stall and create an infinite loop.

Usually fails on: Two-element ranges never converge.

Fix: Use `lo = mid + 1` or `hi = mid - 1` where appropriate.

Shrinking the window only once

Wrong move: Using `if` instead of `while` leaves the window invalid for multiple iterations.

Usually fails on: Over-limit windows stay invalid and produce wrong lengths/counts.

Fix: Shrink in a `while` loop until the invariant is valid again.