2106: Maximum-Fruits-Harvested-After-at-Most-K-Steps
Hard

table of contents

The intuition behind this algorithm is not that hard; just coding it up is a pain in the backside.

For simplicity, if we left-shift all the indices by startPos, we can assume that the question is basically zero-indexed (which will make explaining simpler).

Now, the main intuition is that, if we want to optimally traverse the x-axis, we should make a maximum of only one direction change. That leaves us with only a limited number of windows that we have to check; we can use a sliding window to check this.

For example, given a value of k = 8, we have the options:

8 <= 0      // traverse 8 spaces to the left
6 <= 0 => 1 // traverse 1 spaces to the right, then 7 spaces to the left
4 <= 0 => 2 // traverse 2 spaces to the right, then 6 spaces to the left
2 <= 0 => 3 // traverse 3 spaces to the right, then 5 spaces to the left

// change the direction up!

3 <= 0 => 2 // traverse 3 spaces to the left, then 5 spaces to the right
2 <= 0 => 4 // traverse 2 spaces to the left, then 6 spaces to the right
1 <= 0 => 6 // traverse 1 spaces to the left, then 7 spaces to the right
     0 => 8 // traverse 8 spaces to the right

In essence, we start up with a window where we traverse k spaces to the left. Then, we can just shift our left-index by 2 and our right-index by 1 until the right-index is greater than our left-index.

Afterwards, we reverse our left-index and right-index differences, before shifting our left-index by 1 and our right-index by 2 until the left-index is zero-indexed.

Finally, we can just keep track of our max ans in every sliding window before returning it.

code

class Solution {
public:
    int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) {
        int currSum = 0;
        int leftIndex = 0;
        int leftIndexValue = startPos-k;
        while(leftIndex < fruits.size() && fruits[leftIndex][0] < leftIndexValue) {
            ++leftIndex;
        }

        int rightIndex = leftIndex;
        int rightIndexValue = startPos; 
        while (rightIndex < fruits.size() && fruits[rightIndex][0] <= startPos) {
            currSum += fruits[rightIndex][1];
            ++rightIndex;
        }

        int ans = currSum;
        while (rightIndex < fruits.size() && startPos - leftIndexValue > rightIndexValue - startPos) {
            leftIndexValue += 2;
            rightIndexValue += 1;
            while (fruits[leftIndex][0] < leftIndexValue) {
                currSum -= fruits[leftIndex][1];
                ++leftIndex;
            }
            if (fruits[rightIndex][0] <= rightIndexValue) {
                currSum += fruits[rightIndex][1];
                ++rightIndex;
            }
            ans = max(ans, currSum);
        }

        int incrementValue = 2 * startPos - leftIndexValue - rightIndexValue;
        rightIndexValue += incrementValue;
        while(rightIndex > 0 && fruits[rightIndex-1][0] > rightIndexValue) {
            currSum -= fruits[rightIndex-1][1];
            --rightIndex;
        }

        leftIndexValue += incrementValue;
        while(leftIndex > 0 && fruits[leftIndex-1][0] >= leftIndexValue) {
            currSum += fruits[leftIndex-1][1];
            --leftIndex;
        } 

        ans = max(ans, currSum);
        while (rightIndex < fruits.size() && leftIndexValue < startPos) {
            leftIndexValue += 1;
            rightIndexValue += 2;
            if (fruits[leftIndex][0] < leftIndexValue) {
                currSum -= fruits[leftIndex][1];
                ++leftIndex;
            }
            while (rightIndex < fruits.size() && fruits[rightIndex][0] <= rightIndexValue) {
                currSum += fruits[rightIndex][1];
                ++rightIndex;
            }
            ans = max(ans, currSum);
        }
        
        return ans;
    }
};

complexity

learnings

time taken