How to Solve Fruit into Baskets
Fruit into Baskets Problem
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:
- 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
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: 41def maxFruits(fruits):
2 max_count = 0
3 basket = {}
4 start = 0
5
6 for end in range(len(fruits)):
7 # Add fruit to the basket
8 basket[fruits[end]] = end
9
10 # If there are more than 2 types of fruit in the basket,
11 # remove the fruit that appeared first and update the start index
12 if len(basket) > 2:
13 min_index = min(basket.values())
14 del basket[fruits[min_index]]
15 start = min_index + 1
16
17 # Update the maximum count if the current window is larger
18 max_count = max(max_count, end - start + 1)
19
20 return max_count
21
22fruits1 = ['Apple', 'Banana', 'Orange']
23print(maxFruits(fruits1)) # Output: 2
24
25fruits2 = ['Apple', 'Banana', 'Orange', 'Apple']
26print(maxFruits(fruits2)) # Output: 2
27
28fruits3 = ['Apple', 'Apple', 'Banana', 'Banana', 'Orange', 'Orange']
29print(maxFruits(fruits3)) # Output: 4Time/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.
Watch These Related Mock Interviews
About interviewing.io
interviewing.io 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.
