MEDIUM
DATA STRUCTURES AND ALGORITHMS

# How to Solve Fruit into Baskets

Written By 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:

• 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

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
start = 0

for end in range(len(fruits)):

# If there are more than 2 types of fruit in the basket,
# remove the fruit that appeared first and update the start 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.