Fruit Into Baskets

Problem Statement

Imagine visiting a farm that's arranged in a single row of fruit trees, where each tree is identified by the type of fruit it produces through an integer array called fruits. The goal is to collect as many fruits as possible by adhering to the farm owner's specific rules. You are only equipped with two baskets, and each can only carry one type of fruit, though they have no capacity limit. The task requires you to start from any tree and keep collecting one fruit from each subsequent tree, moving only to the right, until encountering a tree whose fruit type doesn't match the baskets' contents. The challenge is to determine the maximum number of fruits you can collect under these constraints.

Examples

Example 1

Input:

fruits = [1,2,1]

Output:

3

Explanation:

We can pick from all 3 trees.

Example 2

Input:

fruits = [0,1,2,2]

Output:

3

Explanation:

We can pick from trees [1,2,2].
If we had started at the first tree, we would only pick from trees [0,1].

Example 3

Input:

fruits = [1,2,3,2,2]

Output:

4

Explanation:

We can pick from trees [2,3,2,2].
If we had started at the first tree, we would only pick from trees [1,2].

Constraints

• 1 <= fruits.length <= 105
• 0 <= fruits[i] < fruits.length

Approach and Intuition

Let's breakdown the examples to understand the problem and the approach:

1. Initial Observations:

   • The constraints let us use exactly two baskets, and each tree visit must continue in a strictly rightward direction without skipping any trees. Thus, the main problem translates to a version of the maximum subarray issue, where the subarray can only include up to two distinct numbers.

2. Intuition:

   • This is fundamentally a sliding window problem where the window can contain elements of up to two distinct types. The length of this window represents the number of fruits you can collect continuously.
   • Start with an empty window and expand it by moving the right boundary to include new trees.
   • If adding a new tree causes the window to have more than two distinct types of fruits, shift the left boundary of the window inward until you're back to having only two types.

3. Example Walk-through:

   • Example 1: fruits = [1, 2, 1]
     • Able to collect all three trees because these can be accommodated within the two-basket rule.
   • Example 2: fruits = [0, 1, 2, 2]
     • Starting from the second tree (tree with 1), and collecting fruits from trees [1, 2, 2] maximizes the fruit collection to 3. Starting from the first tree would limit the collection to 2 fruits because introducing 2 would require discarding 0, making it inefficient.
   • Example 3: fruits = [1, 2, 3, 2, 2]
     • Best starting from the second tree yields collecting fruits from [2, 3, 2, 2], resulting in four collected fruits.

4. Edge Details:

   • An initial fast pointer (right boundary of our window) to iterate through fruits.
   • Use a hashmap to maintain counts of each type of fruit within the current window.
   • Move a slow pointer (left boundary) to adjust the window when more than two distinct fruits are within the window. Reducing the count of the leftmost fruit and if it drops to zero, remove it from our hashmap to manage our two types constraint effectively.

Solutions

class Solution {
public:
    int gatherMaxFruits(vector<int>& fruitList) {
        // HashMap to record the count of each type of fruit in the current window
        unordered_map<int, int> fruitCount;
        int start = 0, longestLength = 0;
    
        // Process each fruit in the list
        for (int end = 0; end < fruitList.size(); ++end) {
            fruitCount[fruitList[end]]++;
    
            // Ensure there are at most two types of fruits in the window
            while (fruitCount.size() > 2) {
                fruitCount[fruitList[start]]--;
                if (fruitCount[fruitList[start]] == 0)
                    fruitCount.erase(fruitList[start]);
                start++;
            }
    
            // Calculate the length of the current valid window
            longestLength = max(longestLength, end - start + 1);
        }
            
        // Return the largest window found that contains at most two types of fruits
        return longestLength;
    }
};