# Maximum Fruits Harvested After at Most K Steps
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-fruits-harvested-after-at-most-k-steps)
Canonical: https://scaleengineer.com/dsa/problems/maximum-fruits-harvested-after-at-most-k-steps
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [Deutsche Bank](https://scaleengineer.com/companies/deutsche-bank)
---
## Problem
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_.

**Example 1:**

![](https://assets.glich.co/dsa/maximum-fruits-harvested-after-at-most-k-steps/image0.png) 

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

![](https://assets.glich.co/dsa/maximum-fruits-harvested-after-at-most-k-steps/image1.png) 

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

![](https://assets.glich.co/dsa/maximum-fruits-harvested-after-at-most-k-steps/image2.png) 

**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 <= 105`
* `fruits[i].length == 2`
* `0 <= startPos, positioni <= 2 * 105`
* `positioni-1 < positioni` for any `i > 0` (**0-indexed**)
* `1 <= amounti <= 104`
* `0 <= k <= 2 * 105`

# Approaches
## Brute Force with Prefix Sums
The most straightforward approach is to check every possible continuous range of fruits that can be harvested. We can iterate through all possible start and end points of a harvest trip, calculate the cost in steps, and if it's within our budget `k`, we find the sum of fruits and update our maximum.
**Time:** O(N^2), where N is the number of fruit entries. The nested loops iterate through all O(N^2) possible subarrays. All calculations inside the loops take O(1) time. · **Space:** O(N), where N is the number of fruit entries. This is for storing the prefix sum array.
**Pros:** Simple to understand and implement.; Correctly explores all possible harvesting ranges.
**Cons:** The time complexity of O(N^2) is too slow for the given constraints (N up to 10^5), and will likely result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
This method exhaustively checks every possible contiguous block of fruits. A block is defined by a starting index `i` and an ending index `j` from the `fruits` array. For each pair `(i, j)`, we determine the minimum number of steps required to start at `startPos`, visit `fruits[i]`, `fruits[j]`, and all fruits in between. 

The cost of a trip depends on the positions of the interval `[fruits[i][0], fruits[j][0]]` relative to `startPos`. If the interval is entirely to one side, the cost is simply the distance from `startPos` to the farthest point. If the interval spans `startPos`, we must consider two paths: going left first and then crossing over to the right end, or vice-versa. We take the minimum of these two path costs. 

To avoid re-calculating the sum of fruits for each range, which would make the complexity O(N^3), we can pre-compute a prefix sum array. This allows us to find the sum of fruits for any range `[i, j]` in O(1) time. We then compare the fruits collected for each valid trip and keep track of the maximum.

```java
class Solution {
    public int maxTotalFruits(int[][] fruits, int startPos, int k) {
        int n = fruits.length;
        int[] prefixSum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + fruits[i][1];
        }

        int maxFruits = 0;

        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int leftPos = fruits[i][0];
                int rightPos = fruits[j][0];
                int steps = 0;

                if (rightPos <= startPos) { // Go left only
                    steps = startPos - leftPos;
                } else if (leftPos >= startPos) { // Go right only
                    steps = rightPos - startPos;
                } else { // Go both ways
                    int dist1 = 2 * (startPos - leftPos) + (rightPos - startPos);
                    int dist2 = 2 * (rightPos - startPos) + (startPos - leftPos);
                    steps = Math.min(dist1, dist2);
                }

                if (steps <= k) {
                    int currentFruits = prefixSum[j + 1] - prefixSum[i];
                    maxFruits = Math.max(maxFruits, currentFruits);
                }
            }
        }

        return maxFruits;
    }
}
```
### Algorithm
*   Pre-calculate a prefix sum array for the fruit amounts to quickly find the sum of fruits in any given range `[i, j]`.
*   Initialize a variable `maxFruits` to 0.
*   Use nested loops to iterate through every possible continuous subarray of fruits, defined by a start index `i` and an end index `j` (`0 <= i <= j < n`).
*   For each subarray `[i, j]`, let `leftPos = fruits[i][0]` and `rightPos = fruits[j][0]`.
*   Calculate the total steps required to travel from `startPos` and cover the entire range `[leftPos, rightPos]`.
    *   If the entire range is to the right of `startPos` (`startPos <= leftPos`), the cost is `rightPos - startPos`.
    *   If the entire range is to the left of `startPos` (`rightPos <= startPos`), the cost is `startPos - leftPos`.
    *   If the range spans `startPos` (`leftPos < startPos < rightPos`), the cost is the minimum of going left first then right, or right first then left: `min(2 * (startPos - leftPos) + (rightPos - startPos), 2 * (rightPos - startPos) + (startPos - leftPos))`.
*   If the calculated steps are less than or equal to `k`, it's a valid trip. Calculate the total fruits in this range `[i, j]` using the prefix sum array.
*   Update `maxFruits` with the maximum value found so far.
*   After checking all `(i, j)` pairs, return `maxFruits`.

## Iterating Endpoints with Binary Search
We can improve upon the brute-force approach by optimizing the search for the second endpoint of the harvesting range. Instead of a linear scan for the other end, which leads to an O(N^2) complexity, we can use binary search. For a fixed starting direction and a fixed turning point, the farthest reachable point in the other direction is monotonic, which allows for binary search.
**Time:** O(N log N). We iterate through the fruits array once for each case (O(N)), and inside the loop, we perform a binary search (O(log N)). · **Space:** O(N) for the prefix sum array and positions array.
**Pros:** Significantly more efficient than the brute-force approach.; Passes for larger inputs where O(N^2) would fail.
**Cons:** The logic is more complex than brute force, involving two separate cases and binary searches.; Still not the most optimal solution in terms of time complexity.
### Explanation
This approach breaks the problem down into two main scenarios: starting by moving left, or starting by moving right. 

For the first scenario (move left, then right), we iterate through every possible leftmost fruit `fruits[i]` that we might visit. For each `fruits[i]`, we calculate the steps needed to reach it (`startPos - fruits[i][0]`). The cost of the round trip to `fruits[i]` and back to `startPos` is `2 * (startPos - fruits[i][0])`. The remaining steps, `k - 2 * (startPos - fruits[i][0])`, can be used to travel right. This determines a maximum reachable position on the right side. Since the `fruits` array is sorted by position, we can use binary search to efficiently find the rightmost fruit `fruits[j]` that falls within this reachable boundary. The total fruits for the range `[i, j]` are then calculated using a prefix sum array.

The second scenario (move right, then left) is handled symmetrically. We iterate through every possible rightmost fruit `fruits[j]`, calculate the remaining steps for a trip to the left, determine the leftmost reachable position, and use binary search to find the corresponding `fruits[i]`. 

This method effectively reduces the search for the second endpoint from O(N) to O(log N), leading to an overall improved time complexity.

```java
import java.util.Arrays;

class Solution {
    public int maxTotalFruits(int[][] fruits, int startPos, int k) {
        int n = fruits.length;
        int[] positions = new int[n];
        int[] prefixSum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            positions[i] = fruits[i][0];
            prefixSum[i + 1] = prefixSum[i] + fruits[i][1];
        }

        int maxFruits = 0;

        // Case 1: Go left first, then right
        for (int i = 0; i < n; i++) {
            int leftPos = positions[i];
            if (leftPos > startPos + k) break;
            int distLeft = Math.abs(startPos - leftPos);
            if (distLeft > k) continue;
            
            int remaining_k = k - 2 * distLeft;
            if (remaining_k >= 0) {
                int rightBound = startPos + remaining_k;
                int j = findUpperBound(positions, rightBound);
                int currentFruits = prefixSum[j + 1] - prefixSum[i];
                maxFruits = Math.max(maxFruits, currentFruits);
            }
            // Also consider only going left
            if (leftPos <= startPos) {
                 int j = findUpperBound(positions, startPos);
                 int currentFruits = prefixSum[j + 1] - prefixSum[i];
                 maxFruits = Math.max(maxFruits, currentFruits);
            }
        }

        // Case 2: Go right first, then left
        for (int j = 0; j < n; j++) {
            int rightPos = positions[j];
            if (rightPos < startPos - k) continue;
            int distRight = Math.abs(startPos - rightPos);
            if (distRight > k) break;

            int remaining_k = k - 2 * distRight;
            if (remaining_k >= 0) {
                int leftBound = startPos - remaining_k;
                int i = findLowerBound(positions, leftBound);
                int currentFruits = prefixSum[j + 1] - prefixSum[i];
                maxFruits = Math.max(maxFruits, currentFruits);
            }
            // Also consider only going right
            if (rightPos >= startPos) {
                int i = findLowerBound(positions, startPos);
                int currentFruits = prefixSum[j + 1] - prefixSum[i];
                maxFruits = Math.max(maxFruits, currentFruits);
            }
        }

        return maxFruits;
    }

    // Finds index of last element <= val
    private int findUpperBound(int[] arr, int val) {
        int low = 0, high = arr.length - 1, ans = -1;
        while(low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] <= val) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return ans;
    }

    // Finds index of first element >= val
    private int findLowerBound(int[] arr, int val) {
        int low = 0, high = arr.length - 1, ans = arr.length;
        while(low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] >= val) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }
}
```
### Algorithm
*   Pre-calculate a prefix sum array for the fruit amounts.
*   Initialize `maxFruits` to 0.
*   The core idea is to fix one end of the journey and find the optimal other end using binary search.
*   **Case 1: Go left first, then optionally right.**
    *   Iterate through each fruit `fruits[i]` to the left of or at `startPos` as the leftmost point of the journey.
    *   Calculate the distance to go left: `distLeft = startPos - fruits[i][0]`. If `distLeft > k`, we can't reach it, so we can stop.
    *   The total steps for a trip that goes left to `fruits[i]` and then right to `fruits[j]` is `2 * distLeft + (fruits[j][0] - startPos)`. This must be `<= k`.
    *   This gives us the maximum reachable position on the right: `rightBound = startPos + k - 2 * distLeft`.
    *   Use binary search (e.g., `upper_bound`) on the fruit positions to find the index `j` of the rightmost fruit within `rightBound`.
    *   Calculate the fruits in range `[i, j]` and update `maxFruits`.
*   **Case 2: Go right first, then optionally left.**
    *   Symmetrically, iterate through each fruit `fruits[j]` to the right of or at `startPos` as the rightmost point.
    -   Calculate `distRight = fruits[j][0] - startPos`. If `distRight > k`, stop.
    *   The maximum reachable position on the left is `leftBound = startPos - (k - 2 * distRight)`.
    *   Use binary search (e.g., `lower_bound`) to find the index `i` of the leftmost fruit within `leftBound`.
    *   Calculate fruits in `[i, j]` and update `maxFruits`.
*   Return the overall `maxFruits`.

## Sliding Window
The most optimal solution uses the sliding window technique. This approach avoids redundant calculations by intelligently expanding and shrinking a window over the `fruits` array. The key insight is that as we expand the window to the right, the left boundary of the optimal window will never move backward. This monotonicity allows for a linear time solution.
**Time:** O(N), where N is the number of fruit entries. Both the `right` and `left` pointers traverse the array at most once. · **Space:** O(1), as we only use a few variables to keep track of the window pointers and the current sum.
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(1) (excluding input storage).
**Cons:** The logic for the step calculation within the loop can be slightly complex to formulate correctly, with multiple conditions to check.
### Explanation
We can think of the problem as finding the best possible window of fruits `[i, j]` that maximizes the sum of amounts while respecting the step limit `k`. This structure is a perfect fit for a sliding window algorithm.

We use two pointers, `left` and `right`, to define the current window of fruits being considered. The `right` pointer iterates through the `fruits` array from beginning to end, expanding the window one fruit at a time. For each new fruit added, we calculate the cost to harvest all fruits within the current `[left, right]` window.

If the cost exceeds `k`, our window is too 'wide' in terms of travel distance. We must shrink the window from the left by incrementing the `left` pointer until the cost is once again within our budget `k`. As we shrink the window, we subtract the amount of the fruit at the old `left` position from our running sum.

Because both the `left` and `right` pointers only move forward through the array, each fruit is processed a constant number of times. This results in a highly efficient linear time complexity. We can maintain the sum of fruits within the window with a single variable, updating it as we slide, which gives us constant space complexity.

```java
class Solution {
    public int maxTotalFruits(int[][] fruits, int startPos, int k) {
        int n = fruits.length;
        int left = 0;
        int maxFruits = 0;
        int currentSum = 0;

        for (int right = 0; right < n; right++) {
            currentSum += fruits[right][1];

            // Shrink window from the left if it's too costly
            while (left <= right) {
                int leftPos = fruits[left][0];
                int rightPos = fruits[right][0];
                int steps = 0;

                if (rightPos <= startPos) { // Go left only
                    steps = startPos - leftPos;
                } else if (leftPos >= startPos) { // Go right only
                    steps = rightPos - startPos;
                } else { // Go both ways
                    int dist1 = 2 * (startPos - leftPos) + (rightPos - startPos);
                    int dist2 = 2 * (rightPos - startPos) + (startPos - leftPos);
                    steps = Math.min(dist1, dist2);
                }

                if (steps <= k) {
                    break; // Window is valid
                }
                
                // Window is invalid, shrink from left
                currentSum -= fruits[left][1];
                left++;
            }

            maxFruits = Math.max(maxFruits, currentSum);
        }

        return maxFruits;
    }
}
```
### Algorithm
*   Initialize a `left` pointer to 0, `maxFruits` to 0, and `currentSum` to 0.
*   Iterate with a `right` pointer from 0 to `n-1`, expanding a window `[left, right]`.
*   In each iteration, add the fruits at the `right` pointer to `currentSum`: `currentSum += fruits[right][1]`.
*   Calculate the steps required to harvest the fruits in the current window `[left, right]`.
    *   Let `leftPos = fruits[left][0]` and `rightPos = fruits[right][0]`.
    *   The cost calculation is the same as in the brute-force approach, depending on the window's position relative to `startPos`.
*   While the calculated `steps > k` and `left <= right`:
    *   The window is too large/costly. Shrink it from the left.
    *   Subtract the fruits at the `left` pointer from `currentSum`: `currentSum -= fruits[left][1]`.
    *   Increment the `left` pointer: `left++`.
    *   Re-calculate the steps for the new, smaller window.
*   After the while loop, the window `[left, right]` is guaranteed to be valid (i.e., `steps <= k`).
*   Update `maxFruits = max(maxFruits, currentSum)`.
*   After the `right` pointer has traversed the entire array, return `maxFruits`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxTotalFruits(vector<vector<int>> &fruits, int startPos, int k) {
    int ans = 0, s = 0;
    for (int i = 0, j = 0; j < fruits.size(); ++j) {
      int pj = fruits[j][0], fj = fruits[j][1];
      s += fj;
      while (i <= j &&
             pj - fruits[i][0] +
                     min(abs(startPos - fruits[i][0]), abs(startPos - pj)) >
                 k) {
        s -= fruits[i++][1];
      }
      ans = max(ans, s);
    }
    return ans;
  }
};

```

### Python

```python
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

```