Fruit into Baskets (Interview Solution)

How to Solve Fruit into Baskets

Fruit into Baskets Problem

You are given an array of strings representing a sequence of fruit trees e.g. ['Apple', 'Banana', 'Orange']. You have two baskets and you are to pick fruits from the tree and put them into the baskets. Your goal is to return the maximum number of fruit trees you can pick from given the below restrictions

Restrictions:

Example Inputs and Outputs

Example 1

Input: Fruits = ['Apple', 'Banana', 'Orange']
Output: 2

Example 2

Input: Fruits = ['Apple', 'Banana', 'Orange', 'Apple']
Output: 2

Example 3

Input: Fruits = ['Apple', 'Apple', 'Banana', 'Banana', 'Orange', 'Orange']
Output: 4

Fruit into Baskets Solutions

To solve this problem, we can use a sliding window approach. We'll imagine a window that can move through the array of fruit trees. The window starts at the beginning and expands by adding fruits to our "basket" as we encounter them. We'll keep track of the types of fruits in the basket and their corresponding indices. If the number of fruit types exceeds two, it means we need to adjust the window. We'll remove the fruit that appeared first in our basket and update the start position accordingly. We'll also keep track of the maximum number of fruit trees we've seen so far by comparing the size of the current window with the previous maximum count. This approach allows us to find the maximum number of fruit trees we can pick while following the given restrictions.

Python Code

def maxFruits(fruits):
    max_count = 0
    basket = {}
    start = 0

for end in range(len(fruits)):
        # Add fruit to the basket
        basket[fruits[end]] = end

# If there are more than 2 types of fruit in the basket,
        # remove the fruit that appeared first and update the start index
        if len(basket) > 2:
            min_index = min(basket.values())
            del basket[fruits[min_index]]
            start = min_index + 1

# Update the maximum count if the current window is larger
        max_count = max(max_count, end - start + 1)

return max_count

fruits1 = ['Apple', 'Banana', 'Orange']
print(maxFruits(fruits1))  # Output: 2

fruits2 = ['Apple', 'Banana', 'Orange', 'Apple']
print(maxFruits(fruits2))  # Output: 2

fruits3 = ['Apple', 'Apple', 'Banana', 'Banana', 'Orange', 'Orange']
print(maxFruits(fruits3))  # Output: 4

Time/Space Complexity Analysis