Fruit Into Baskets

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

The "Fruit Into Baskets" problem is efficiently tackled using a sliding window technique coupled with a hashmap to maintain a count of each fruit type over the window. Below is a concise explanation of the solution:

• The function gatherMaxFruits uses unordered_map<int, int> named fruitCount to track the number of each type of fruit in the current window bounded by start and end.
• Iterate through each fruit in fruitList using a loop, increasing the count of the current fruit in fruitCount.
• Continue adjusting the window by verifying that only two types of fruits are present. If more types are present, adjust start to reduce the window's size and update the hashmap accordingly.
• Keep track of the maximum window size that meets the criteria using the variable longestLength.
• After processing all fruits, return longestLength, which will be the maximum number of fruits you can gather in two baskets.

By adjusting the window size and position while iterating through the fruits, you ensure time-efficient processing of the input, giving an optimal solution to the problem.

class Solution {
    public int maxTwoFruits(int[] tree) {
        Map<Integer, Integer> fruitCount = new HashMap<>();
        int start = 0, maxFruit = 0;
        
        for (int end = 0; end < tree.length; end++) {
            fruitCount.put(tree[end], fruitCount.getOrDefault(tree[end], 0) + 1);

            while (fruitCount.size() > 2) {
                fruitCount.put(tree[start], fruitCount.get(tree[start]) - 1);
                if (fruitCount.get(tree[start]) == 0)
                    fruitCount.remove(tree[start]);
                start++;
            }
            
            maxFruit = Math.max(maxFruit, end - start + 1);
        }
        
        return maxFruit;
    }
}

This Java solution is designed to solve the "Fruit Into Baskets" problem, which aims to find the maximum number of fruits you can collect by collecting from only two types of trees in a row. The method in the solution, maxTwoFruits, utilizes the sliding window technique with a HashMap to handle the counting of fruits from different types of trees.

• A HashMap named fruitCount keeps track of the count of each type of fruit encountered.
• Two pointers, start and end, are used to define the current window of fruit trees being considered.
• As end traverses through the tree array, fruits are added to fruitCount and their occurrences are updated.
• The while loop ensures that if the basket contains more than two types of fruits, the start pointer adjusts back until only two types remain in the fruitCount map. This effectively shrinks the window from the left.
• The length of the current window (end - start + 1) is checked against maxFruit to possibly update the maximum number of fruits that can be collected in two baskets.

This technique efficiently solves the problem with a time complexity of O(n), where n is the number of trees, since each element is processed at most twice. The use of the HashMap facilitates quick updates and checks for the fruit types, making it an optimal solution for problems involving constraints on distinct elements in a contiguous subarray.

class Solution:
    def maxFruits(self, tree: List[int]) -> int:
        fruit_count = {}
        max_collected = 0
        window_start = 0
        
        for window_end in range(len(tree)):
            fruit_count[tree[window_end]] = fruit_count.get(tree[window_end], 0) + 1
            
            while len(fruit_count) > 2:
                fruit_count[tree[window_start]] -= 1
                if fruit_count[tree[window_start]] == 0:
                    del fruit_count[tree[window_start]]
                window_start += 1
            
            max_collected = max(max_collected, window_end - window_start + 1)
        
        return max_collected

The provided Python code solves the problem of finding the maximum number of fruits you can collect with two baskets, where each basket can hold any number of a single type of fruit.

• The function maxFruits defines within the class Solution, takes a list tree representing types of fruits sequentially on a row of trees.
• Using a sliding window approach combined with a hash map, fruit_count, the function efficiently tracks the count of each fruit within the current window.
• Starting with a window defined by window_start and expanding with window_end, the code updates the fruit counts as the window expands.
• If the number of unique fruits exceeds 2 (indicating more than two types of fruits in the baskets), the window is adjusted by moving window_start to the right until only two types of fruits are within the window.
• During each iteration, it updates the max_collected value, which keeps track of the maximum number of fruits collected when the condition of holding up to two types of fruits is met.
• Finally, the function returns the value of max_collected, which represents the maximum number of fruits that can be collected with the given basket condition.

This approach ensures the solution is optimal and operates within a time complexity of O(n), where n is the number of trees (or fruits) in the list, due to the efficient management of the sliding window and immediate access to the fruit counts using the hash map.