# LC 2106. Maximum Fruits Harvested After at Most K Steps

### [Problem link](https://leetcode.com/problems/maximum-fruits-harvested-after-at-most-k-steps/)

###### tags: `leedcode` `hard` `c++` `Sliding Window`

Fruits are available at some positions on an infinite x-axis. You are given a 2D integer array <code>fruits</code> where <code>fruits[i] = [position_i, amount_i]</code> depicts <code>amount_i</code> fruits at the position <code>position_i</code>. <code>fruits</code> is already **sorted** by <code>position_i</code> in **ascending order** , and each <code>position_i</code> is **unique** .

You are also given an integer <code>startPos</code> and an integer <code>k</code>. Initially, you are at the position <code>startPos</code>. 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** <code>k</code> 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:**
<img alt="" src="https://assets.leetcode.com/uploads/2021/11/21/1.png" style="width: 472px; height: 115px;" />

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:**
<img alt="" src="https://assets.leetcode.com/uploads/2021/11/21/2.png" style="width: 512px; height: 129px;" />

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:**
<img alt="" src="https://assets.leetcode.com/uploads/2021/11/21/3.png" style="width: 476px; height: 100px;" />

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

- <code>1 <= fruits.length <= 10⁵</code>
- <code>fruits[i].length == 2</code>
- <code>0 <= startPos, position_i <= 2 * 10⁵</code>
- <code>position_i-1 < position_i</code> for any <code>i > 0</code>( **0-indexed** )
- <code>1 <= amount_i <= 10⁴</code>
- <code>0 <= k <= 2 * 10⁵</code>

## Solution 1 - Sliding Window
#### C++

class Solution {
public:
    int calStep(vector<vector<int>>& fruits, int startPos, int l, int r) {
        // 先走左邊再走右邊總長度: (startPos - fruits[l][0]) + (fruits[r][0] - fruits[l][0])
        // = startPos + fruits[r][0] - fruits[l][0] * 2
        // 先走右邊再走左邊總長度: (fruits[r][0] - startPos) + (fruits[r][0] - fruits[l][0])
        // = fruits[r][0] * 2 - startPos - fruits[l][0]
        int a = startPos + fruits[r][0] - fruits[l][0] * 2;
        int b = fruits[r][0] * 2 - startPos - fruits[l][0];
        return min(a, b);
    }

    int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) {
        int l = lower_bound(fruits.begin(), fruits.end(), startPos - k, [](const vector<int>& a, int b) {
            return a[0] < b;
        }) - fruits.begin();

        int sum = 0;
        int r = l;
        while (r < fruits.size() && fruits[r][0] <= startPos) {
            sum += fruits[r][1];
            r++;
        }

        int ans = sum;
        while (r < fruits.size() && fruits[r][0] <= startPos + k) {
            sum += fruits[r][1];
            while (calStep(fruits, startPos, l, r) > k) {
                sum -= fruits[l][1];
                l++;
            }
            ans = max(ans, sum);
            r++;
        }
        return ans;
    }
};

>### Complexity
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n) | O(1) |

## Note
[ref.](https://leetcode.cn/problems/maximum-fruits-harvested-after-at-most-k-steps/solutions/2254860/hua-dong-chuang-kou-jian-ji-xie-fa-pytho-1c2d/)