Fruits Into Baskets

Sliding Window

Problem

Given an array of characters where each character represents a fruit tree, you are given two baskets, and your goal is to put maximum number of fruits in each basket. The only restriction is that each basket can have only one type of fruit.

You can start with any tree, but you can’t skip a tree once you have started. You will pick one fruit from each tree until you cannot, i.e., you will stop when you have to pick from a third fruit type.

Write a function to return the maximum number of fruits in both the baskets.

For example:

Input: Fruit=['A', 'B', 'C', 'A', 'C']
Output: 3
Explanation: We can put 2 'C' in one basket 
and one 'A' in the other from the subarray 
['C', 'A', 'C']

Input: Fruit=['A', 'B', 'C', 'B', 'B', 'C']
Output: 5
Explanation: We can put 3 'B' in one basket 
and two 'C' in the other basket. This can be 
done if we start with the second letter: 
['B', 'C', 'B', 'B', 'C']

Thought Process

• This question is very similar to Longest Substring with K Distinct Characters but in this problem it's the longest subarray with 2 distinct characters (i.e fruits)

• In this problem we need to find the length of the longest subarray with no more than two distinct characters (or fruit types!)

• Use a dictionary so we can keep track of how many fruits we have

Solution

class Solution:
    def totalFruit(self, tree: List[int]) -> int:
        fruitBasket = {}
        maxLength = 0
        start = 0
        
        for i in range(len(tree)):
            if tree[i] not in fruitBasket:
                fruitBasket[tree[i]] = 1
            fruitBasket[tree[i]] +=1
            
            while len(fruitBasket) > 2:
                leftFruit = tree[start]
                fruitBasket[leftFruit]-=1
                if fruitBasket[leftFruit] == 1:
                    del fruitBasket[leftFruit]
                start+=1
            
            maxLength = max(maxLength, i - start + 1)
            
        return maxLength
        

Key Points

• This problem can be represented as we need to find the longest subarray with no more than 2 distnct elements.

• We are using a static window but according to the condition that there must be only 2 distinct characters in this window, which we will know is true or not according to our dictionary length.

• We are using a dictionary to keep track of the number of distinct fruits.

Time Complexity

• Time: $O(n)$

• Space: $O(1)$as there can be a maximum of three types of fruit stored in the frequency map. It's not O(K) because we already know K, which is 2.