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.

&nbsp;
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.


&nbsp;
Constraints:


	1 &lt;= fruits.length &lt;= 105
	fruits[i].length == 2
	0 &lt;= startPos, positioni &lt;= 2 * 105
	positioni-1 &lt; positioni for any i &gt; 0&nbsp;(0-indexed)
	1 &lt;= amounti &lt;= 104
	0 &lt;= k &lt;= 2 * 105


class Solution:
    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:
        arr = [0 for _ in range(2*k+1)]
        for pos, numOfFruit in fruits:
            if pos < startPos-k or pos > startPos+k:
                continue
            arr[pos-(startPos-k)] += numOfFruit

        left, right = sum(arr[:k+1]), sum(arr[k:])
        maxSeen = max(left, right)

        turn = 1 # turning point
        for i in range(2, k+1, 2):
            left = left-arr[i-2]-arr[i-1]+arr[k+turn]
            right = right-arr[~(i-2)]-arr[~(i-1)]+arr[k-turn]
            maxSeen = max(maxSeen, left, right)
            turn += 1

        return maxSeen
class Solution {
    public int maxTotalFruits(int[][] fruits, int startPos, int k) {
        int n = fruits.length;
        int posOfLastFruit = fruits[n-1][0];
        int prefixArr[] = new int[posOfLastFruit + 1];
        int start = Math.max(startPos - k, 0);
        int end = Math.min(startPos + k, prefixArr.length-1);

        if(startPos > posOfLastFruit) {
            int diff = startPos - posOfLastFruit;
            startPos = posOfLastFruit;
             k = k - diff;
            if(k == 0)
                return fruits[posOfLastFruit][1];
            else if(k < 0)
                return 0;
        }

        for(int i = 0 ; i < n ; i++) {
            prefixArr[fruits[i][0]] = fruits[i][1];
        }

        int curr = 0;
        for(int i = startPos-1 ; i >= start ; i--) {
            curr += prefixArr[i];
            prefixArr[i] = curr;
        }

        curr = 0;
        for(int i = startPos+1 ; i <= end ; i++) {
            curr += prefixArr[i];
            prefixArr[i] = curr;
        }

        int minimum = prefixArr[startPos];
        prefixArr[startPos] = 0;
        int ans = 0;

        for(int i = start ; i < startPos ; i++) {
            int maxCurrPossible = prefixArr[i];
            int stepsAlreadyWalked = startPos - i;
            int stepsRemaining = k - stepsAlreadyWalked;
            int endIndex = i + stepsRemaining;

            if(endIndex > startPos && endIndex < prefixArr.length) {
                maxCurrPossible += prefixArr[endIndex];
            } else if(endIndex >= prefixArr.length) {
                maxCurrPossible += prefixArr[prefixArr.length-1];
            }

            ans = Math.max(ans, maxCurrPossible);
        }

        for(int i = startPos+1 ; i <= end ; i++) {
            int maxCurrPossible = prefixArr[i];
            int stepsAlreadyWalked = i - startPos;
            int stepsRemaining = k - stepsAlreadyWalked;
            int endIndex = i - stepsRemaining;

            if(endIndex < startPos && endIndex >= 0) {
                maxCurrPossible += prefixArr[endIndex];
            } else if(endIndex < 0) {
                maxCurrPossible += prefixArr[0];
            }

            ans = Math.max(ans, maxCurrPossible);
        }

        return ans + minimum;
    }
}
class Solution {
public:
    int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) {
        vector<int> arr;
        for (int i=0; i<2*k+1; ++i) {
            arr.push_back(0);
        }

        for (int i=0; i<fruits.size(); ++i) {
            if ((fruits[i][0] < startPos-k) || (fruits[i][0] > startPos+k)) continue;
            arr[fruits[i][0]-(startPos-k)] += fruits[i][1];
        }

        int left = 0, right = 0;
        for (int i = 0; i <= k; ++i) {
            left += arr[i];
            right += arr[k+i];
        }
        int maxSeen = max(left, right);
        int L = arr.size();
        int turn = 1;
        for (int i = 2; i < k+1; i += 2) {
            left = left+arr[k+turn]-arr[i-1]-arr[i-2];
            right = right+arr[k-turn]-arr[L-1-(i-1)]-arr[L-1-(i-2)];
            if (left > maxSeen) maxSeen = left;
            if (right > maxSeen) maxSeen = right;
            turn++;
        }
        return maxSeen;

    }
};
/**
 * @param {number[][]} fruits
 * @param {number} startPos
 * @param {number} k
 * @return {number}
 */
var maxTotalFruits = function(fruits, startPos, k) {
    
    let n = Math.max(fruits[fruits.length-1][0], startPos)+1;
    let numFruits = new Array(n).fill(0);
    let sums = new Array(n).fill(0);
    for(let obj of fruits) {
        let [pos, num] = obj;
        numFruits[pos] = num;
    }
    sums[startPos] = numFruits[startPos] ;
    for(let i = startPos+1; i < n && i <= startPos + k; i++) {
        sums[i] = sums[i-1] + numFruits[i];
    }
    for(let i = startPos-1; i >=0 && i >= startPos - k; i--) {
        sums[i] = sums[i+1] + numFruits[i];
    }
    //console.log(sums);
    let output = 0;
    for(let leftMoves = k; leftMoves >= 0; leftMoves--) {
        let rightMoves = Math.max(k - 2*leftMoves, 0);
        let leftPos = Math.max(0, startPos - leftMoves);
        let rightPos = Math.min(n-1, startPos + rightMoves);
        let count = sums[leftPos] + sums[rightPos] - sums[startPos];
        output = Math.max(output, count);
    }
    for(let rightMoves = k; rightMoves >= 0; rightMoves--) {
        let leftMoves = Math.max(k - 2*rightMoves, 0);
        let leftPos = Math.max(0, startPos - leftMoves);
        let rightPos = Math.min(n-1, startPos + rightMoves);
        let count = sums[leftPos] + sums[rightPos] - sums[startPos];
        output = Math.max(output, count);
    }
    return output;
};
Maximum Fruits Harvested After at Most K Steps