Fruit Into Baskets - Leetcode Solution

The Fruit Into Baskets problem on LeetCode asks us to find the maximum number of fruits we can collect given that we have 2 baskets and each basket can hold only one type of fruit. We are given an array of integers where each integer represents the type of fruit. Our task is to find the length of the longest subarray that contains only two types of fruits.

Let's walk through the solution step by step:

1. We initialize two variables: maxFruits and typesCount. maxFruits will keep track of the maximum number of fruits we can collect and typesCount will keep track of the types of fruit currently in the basket.

2. We initialize two pointers: start and end. Both start and end will initially be at the first element of the array.

3. We create a while loop that will run until the end pointer reaches the end of the array. Inside the loop, we check if the current fruit at the end pointer is already in the basket. If it is, we simply increment the end pointer and continue to the next iteration. If it is not, we need to check if we can add another type of fruit to the basket. If we can, we add the fruit to the basket, increment typesCount, and move the end pointer. If we can't add another fruit to the basket, we move the start pointer, remove the fruit from the basket (decrement typesCount), and continue to move the start pointer until it reaches the position where we can add another fruit to the basket.

4. At every iteration, we also update the maxFruits variable to keep track of the maximum number of fruits we can collect.

5. After the loop ends, we return the maxFruits variable as our solution.

Here is the Python code for the solution:

def totalFruit(tree: List[int]) -> int:
    maxFruits = 0
    typesCount = 0  # number of types we have in the basket
    baskets = {}
    start = end = 0
    
    while end < len(tree):
        fruit = tree[end]
        if fruit in baskets:
            baskets[fruit] += 1
        else:
            if typesCount < 2:
                baskets[fruit] = 1
                typesCount += 1
            else:
                # we need to remove a fruit from the basket
                while typesCount >= 2:
                    basketFruit = tree[start]
                    baskets[basketFruit] -= 1
                    if baskets[basketFruit] == 0:
                        typesCount -= 1
                        del baskets[basketFruit]
                    start += 1
                baskets[fruit] = 1
                typesCount += 1
        end += 1
        maxFruits = max(maxFruits, end - start)
    
    return maxFruits

The time complexity of this solution is O(n) because we iterate through the array only once. The space complexity is O(1) because we only store two types of fruits in the basket at any given time.

1