title: Maximum Fruits Harvested After at Most K Steps
slug: maximum-fruits-harvested-after-at-most-k-steps
difficulty: hard
leetcode_id: 2106
leetcode_url: https://leetcode.com/problems/maximum-fruits-harvested-after-at-most-k-steps/
categories:
  - arrays
  - binary-search
patterns:
  - slug: sliding-window
    is_optimal: true
  - slug: prefix-sum
    is_optimal: false
  - slug: two-pointers
    is_optimal: false

function_signature: "def max_total_fruits(fruits: list[list[int]], start_pos: int, k: int) -> int:"

test_cases:
  visible:
    - input: { fruits: [[2, 8], [6, 3], [8, 6]], start_pos: 5, k: 4 }
      expected: 9
    - input: { fruits: [[0, 9], [4, 1], [5, 7], [6, 2], [7, 4], [10, 9]], start_pos: 5, k: 4 }
      expected: 14
    - input: { fruits: [[0, 3], [6, 4], [8, 5]], start_pos: 3, k: 2 }
      expected: 0
  hidden:
    - input: { fruits: [[0, 10]], start_pos: 0, k: 0 }
      expected: 10
    - input: { fruits: [[5, 5]], start_pos: 5, k: 0 }
      expected: 5
    - input: { fruits: [[0, 5], [10, 5]], start_pos: 5, k: 5 }
      expected: 5
    - input: { fruits: [[1, 1], [2, 2], [3, 3]], start_pos: 2, k: 10 }
      expected: 6

description: |
  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*.

constraints: |
  - `1 <= fruits.length <= 10^5`
  - `fruits[i].length == 2`
  - `0 <= startPos, position_i <= 2 * 10^5`
  - `position_i-1 < position_i` for any `i > 0` (0-indexed)
  - `1 <= amount_i <= 10^4`
  - `0 <= k <= 2 * 10^5`

examples:
  - input: "fruits = [[2,8],[6,3],[8,6]], startPos = 5, k = 4"
    output: "9"
    explanation: "Move right to position 6 (harvest 3 fruits), then right to position 8 (harvest 6 fruits). Total: 3 + 6 = 9 fruits in 3 steps."
  - input: "fruits = [[0,9],[4,1],[5,7],[6,2],[7,4],[10,9]], startPos = 5, k = 4"
    output: "14"
    explanation: "Harvest 7 at position 5, move left to 4 (harvest 1), move right to 6 (harvest 2), move right to 7 (harvest 4). Total: 7 + 1 + 2 + 4 = 14 fruits in 4 steps."
  - input: "fruits = [[0,3],[6,4],[8,5]], startPos = 3, k = 2"
    output: "0"
    explanation: "With only 2 steps from position 3, you cannot reach any position with fruits."

explanation:
  intuition: |
    Picture yourself standing at `startPos` on a number line with fruit baskets scattered at various positions. You have exactly `k` steps to spend, and you want to collect as many fruits as possible.

    The key insight is that **optimal paths follow a specific pattern**: you either go left first then right, or right first then left, or only in one direction. You never benefit from changing direction more than once because backtracking wastes steps.

    Think of it like this: if you walk `x` steps left and then turn around to walk `y` steps right, you've used `x + x + y = 2x + y` steps (you traverse the left portion twice). Similarly, going right first then left uses `2y + x` steps.

    This means for any contiguous segment `[left, right]` of fruit positions that we want to harvest:
    - If `left < startPos < right`, we must turn around once
    - The cost is `min(2 * (startPos - left) + (right - startPos), 2 * (right - startPos) + (startPos - left))`
    - We pick the direction that minimises backtracking

    Since we want to maximise fruits within a step budget, we can use a **sliding window** over the sorted fruit positions, expanding and shrinking to find the maximum sum where the path cost stays within `k`.

  approach: |
    We solve this using a **Sliding Window with Two Pointers**:

    **Step 1: Build a prefix sum array**

    - Create a prefix sum of fruit amounts to quickly compute the sum of any contiguous range
    - `prefix[i]` = total fruits from index `0` to `i-1`

    &nbsp;

    **Step 2: Define the step cost function**

    - For a window `[left, right]` of fruit positions, calculate the minimum steps needed:
    - If both positions are on the same side of `startPos`, cost is simply the distance to the farther one
    - If `startPos` is between them, cost is `min(2 * left_dist + right_dist, left_dist + 2 * right_dist)`
    - This accounts for going one direction, then backtracking

    &nbsp;

    **Step 3: Slide the window**

    - Use two pointers `left` and `right` to define the current window of fruit positions
    - Expand `right` to include more fruits
    - When the step cost exceeds `k`, shrink from `left`
    - Track the maximum fruit sum across all valid windows

    &nbsp;

    **Step 4: Return the maximum**

    - The answer is the maximum sum found across all valid windows

  common_pitfalls:
    - title: Treating This as a Simple Range Problem
      description: |
        A common mistake is to think you can simply harvest all fruits within distance `k` from `startPos`. This ignores the backtracking cost.

        For example, if `startPos = 5`, `k = 4`, and fruits are at positions `3` and `8`:
        - Distance to `3` is `2`, distance to `8` is `3`
        - But visiting both requires going left 2 steps, then right 5 steps = 7 total steps, exceeding `k = 4`

        You must account for the **round-trip cost** when collecting fruits on both sides.
      wrong_approach: "Collect all fruits within distance k"
      correct_approach: "Calculate actual path cost including backtracking"

    - title: Checking All Possible Paths Naively
      description: |
        Trying every possible `(left_distance, right_distance)` combination and summing fruits leads to **O(n * k)** or worse complexity.

        With `n = 10^5` and `k = 2 * 10^5`, this approach will TLE.

        The sliding window approach reduces this to O(n) by maintaining a valid window and never re-scanning already-processed positions.
      wrong_approach: "Enumerate all possible left/right distances"
      correct_approach: "Sliding window with two pointers"

    - title: Forgetting to Handle Single-Direction Paths
      description: |
        When all reachable fruits are on one side of `startPos`, the cost is simply the distance to the farthest fruit (no backtracking).

        Make sure your cost function handles:
        - All fruits to the left: cost = `startPos - leftmost_position`
        - All fruits to the right: cost = `rightmost_position - startPos`
        - Fruits on both sides: cost = minimum of two turn-around strategies

  key_takeaways:
    - "**Sliding window on sorted data**: When the array is sorted and you need to find an optimal contiguous segment, sliding window is often the key"
    - "**Turn-around costs matter**: In path problems, backtracking doubles the distance for that segment"
    - "**Prefix sums for range queries**: Precompute cumulative sums to get O(1) range sum queries"
    - "**Two-pointer optimisation**: The monotonic nature of the cost function allows us to shrink/expand the window efficiently"

  time_complexity: "O(n). Each fruit position is visited at most twice (once when expanding, once when shrinking the window)."
  space_complexity: "O(n). We store a prefix sum array of size `n + 1`."

solutions:
  - approach_name: Sliding Window with Two Pointers
    is_optimal: true
    code: |
      def max_total_fruits(fruits: list[list[int]], start_pos: int, k: int) -> int:
          n = len(fruits)

          # Build prefix sum for quick range sum queries
          prefix = [0] * (n + 1)
          for i in range(n):
              prefix[i + 1] = prefix[i] + fruits[i][1]

          def get_sum(left: int, right: int) -> int:
              """Get sum of fruits from index left to right (inclusive)."""
              return prefix[right + 1] - prefix[left]

          def min_steps(left_pos: int, right_pos: int) -> int:
              """Calculate minimum steps to visit positions from left_pos to right_pos."""
              # If start is to the right of all positions, just go left
              if start_pos >= right_pos:
                  return start_pos - left_pos
              # If start is to the left of all positions, just go right
              if start_pos <= left_pos:
                  return right_pos - start_pos
              # Start is in between - must turn around once
              left_dist = start_pos - left_pos
              right_dist = right_pos - start_pos
              # Go left first then right, or right first then left
              return min(2 * left_dist + right_dist, left_dist + 2 * right_dist)

          max_fruits = 0
          left = 0

          for right in range(n):
              # Shrink window while steps exceed budget
              while left <= right and min_steps(fruits[left][0], fruits[right][0]) > k:
                  left += 1

              # Update maximum if window is valid
              if left <= right:
                  max_fruits = max(max_fruits, get_sum(left, right))

          return max_fruits
    explanation: |
      **Time Complexity:** O(n) — Each index is processed at most twice by the two pointers.

      **Space Complexity:** O(n) — Prefix sum array of size `n + 1`.

      We slide a window over fruit positions, expanding the right boundary and shrinking the left when the path cost exceeds `k`. The prefix sum allows O(1) range sum queries. The key insight is that as `right` increases, the minimum valid `left` only increases (monotonic), enabling the two-pointer technique.

  - approach_name: Binary Search for Each Right Boundary
    is_optimal: false
    code: |
      def max_total_fruits(fruits: list[list[int]], start_pos: int, k: int) -> int:
          import bisect

          n = len(fruits)
          positions = [f[0] for f in fruits]

          # Build prefix sum
          prefix = [0] * (n + 1)
          for i in range(n):
              prefix[i + 1] = prefix[i] + fruits[i][1]

          def get_sum(left: int, right: int) -> int:
              if left > right or left < 0 or right >= n:
                  return 0
              return prefix[right + 1] - prefix[left]

          max_fruits = 0

          # Try each position as the rightmost point
          for right in range(n):
              right_pos = fruits[right][0]

              # Case 1: Go right first, then left
              # Steps = 2 * (right_pos - start_pos) + (start_pos - left_pos)
              # left_pos >= start_pos - (k - 2 * (right_pos - start_pos))
              if right_pos >= start_pos:
                  remaining = k - (right_pos - start_pos)
                  if remaining >= 0:
                      # Can go left by remaining // 2 after going right
                      left_reach = start_pos - remaining // 2
                      left_idx = bisect.bisect_left(positions, left_reach)
                      max_fruits = max(max_fruits, get_sum(left_idx, right))

              # Case 2: Go left first, then right
              # We handle this by trying each position as leftmost
              # (Symmetric logic)

          # Try each position as the leftmost point
          for left in range(n):
              left_pos = fruits[left][0]

              if left_pos <= start_pos:
                  remaining = k - (start_pos - left_pos)
                  if remaining >= 0:
                      right_reach = start_pos + remaining // 2
                      right_idx = bisect.bisect_right(positions, right_reach) - 1
                      max_fruits = max(max_fruits, get_sum(left, right_idx))

          return max_fruits
    explanation: |
      **Time Complexity:** O(n log n) — Binary search for each of the n positions.

      **Space Complexity:** O(n) — Prefix sum and positions arrays.

      For each position, we use binary search to find the farthest reachable position in the opposite direction given the remaining step budget. This is correct but slightly slower than the two-pointer approach. The two-pointer method exploits the monotonic relationship between boundaries.
