Fruit Into Baskets
Asked at Amazon, Netflix, Salesforce
Problem
Given a row of trees where each tree has a type of fruit, find the maximum number of fruits you can collect with two baskets. Each basket can hold only one type of fruit. This is the longest subarray with at most 2 distinct elements.
Asked At
| Company | Difficulty | |
|---|---|---|
| Amazon | Medium | View all Amazon questions → |
| Netflix | Medium | View all Netflix questions → |
| Salesforce | Medium | View all Salesforce questions → |
How to Think About It
The two baskets represent a sliding window that can contain at most 2 distinct fruit types. Use a hash map to track counts of each type in the current window.
Expand the window (right pointer) to include new trees. When the hash map has more than 2 types, shrink from the left until only 2 types remain.
Track the maximum window size throughout. The answer is the largest window with at most 2 distinct types.
Why it works: the hash map counts how many of each type are in the window. When a third type enters, remove the leftmost type by decrementing its count and moving the left pointer.
Visual walkthrough for [1,2,1], 2 baskets:
Window: [1] → map={1:1}, types=1, max=1
Window: [1,2] → map={1:1,2:1}, types=2, max=2
Window: [1,2,1] → map={1:2,2:1}, types=2, max=3
Result: 3.
Visual walkthrough for [0,1,2,2]:
Window: [0] → map={0:1}, types=1, max=1
Window: [0,1] → map={0:1,1:1}, types=2, max=2
Window: [0,1,2] → map={0:1,1:1,2:1}, types=3. Shrink: remove 0 → map={1:1,2:1}, max=2.
Window: [1,2,2] → map={1:1,2:2}, types=2, max=3.
Result: 3.
Edge cases: array length 1 or 2 (return the length), all same type (return entire length).
Optimal Approach
Step 1: Use a hash map to track fruit counts in the current window.
Step 2: Expand right pointer. Add fruits[right] to the map.
Step 3: While the map has more than 2 keys (types):
Decrement map[fruits[left]]
If count reaches 0, delete the key
Increment left
Step 4: Update max window size: max(max, right - left + 1).
Time: O(n) — each element is visited at most twice (once by right, once by left). Space: O(1) — the map holds at most 3 keys at any time.
What Trips People Up in Real Interviews
Not recognizing this as a sliding window problem. The "two baskets" constraint means at most 2 distinct elements in the window.
Using a fixed-size window. The window size varies, so use a variable-size sliding window with a hash map.
Forgetting to remove keys from the hash map when their count reaches 0. Otherwise, len(count) overcounts the number of distinct types.
Re-initializing the hash map when shrinking. Keep the hash map persistent across the entire scan. Shrinking should decrement counts, not reset.
Confusing "at most 2 types" with "exactly 2 types." The window can have 1 or 2 types. Both are valid.
Solution Code
from collections import defaultdict
def totalFruit(fruits):
count = defaultdict(int)
left = 0
best = 0
for right, fruit in enumerate(fruits):
count[fruit] += 1
while len(count) > 2:
count[fruits[left]] -= 1
if count[fruits[left]] == 0:
del count[fruits[left]]
left += 1
best = max(best, right - left + 1)
return bestFrequently Asked Questions
What is the Fruit Into Baskets problem?
Given a row of trees where each tree has a type of fruit, find the maximum number of fruits you can collect with two baskets. Each basket can hold only one type of fruit. This is the longest subarray with at most 2 distinct elements.
How do you solve Fruit Into Baskets?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Fruit Into Baskets?
Fruit Into Baskets is asked at Amazon, Netflix, Salesforce. It is a medium difficulty problem.
What are common mistakes on Fruit Into Baskets?
- Not recognizing this as a sliding window problem. The "two baskets" constraint means at most 2 distinct elements in the window.
- Using a fixed-size window. The window size varies, so use a variable-size sliding window with a `hash map`.
- Forgetting to remove keys from the `hash map` when their count reaches 0. Otherwise, `len(count)` overcounts the number of distinct types.
- Re-initializing the `hash map` when shrinking. Keep the `hash map` persistent across the entire scan. Shrinking should decrement counts, not reset.
- Confusing "at most 2 types" with "exactly 2 types." The window can have 1 or 2 types. Both are valid.