How to Solve Fruit into Baskets

Written By
Adam Bhula

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


  • You can only have one type of fruit in each basket
  • once you start picking you can't skip a tree and then keep picking

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.

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

  • Time Complexity: O(N), where N is the number of fruits in the input array. The function iterates through the fruits once, performing constant-time operations for each fruit. Therefore, the time complexity is linear with respect to the size of the input.
  • Space Complexity: O(1), as the space occupied by our variables remains constant regardless of the size of the input.

About is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.

We know exactly what to do and say to get the company, title, and salary you want.

Interview prep and job hunting are chaos and pain. We can help. Really.