904. Fruit Into Baskets
Asked at Amazon, Netflix, Salesforce, TikTok
Difficulty
Medium
Time
O(n)
Space
O(1)
Pattern
Array
Companies
4
Problem
You walk along a row of fruit trees from left to right. Each tree grows one type of fruit, given by the array fruits, where fruits[i] is the type of the i-th tree.
You carry two baskets. Each basket can hold only one fruit type, but it can hold any number of that type. Starting at any tree you like, you pick one fruit from that tree and keep moving right, picking one fruit from every tree you pass. Every fruit you pick must fit into one of your two baskets. The moment you reach a tree whose fruit does not fit, you must stop.
Return the maximum number of fruits you can pick. In other words, find the longest run of neighboring trees that contains at most 2 distinct fruit types.
Pick a run with at most 2 types
Constraints
- ●
1 <= fruits.length <= 10^5 - ●
0 <= fruits[i] < fruits.length
Examples
fruits = [1,2,1]3fruits = [0,1,2,2]3fruits = [1,2,3,2,2]4Asked At
4 companies| Company | Difficulty | |
|---|---|---|
| Amazon | Medium | View all Amazon questions → |
| Netflix | Medium | View all Netflix questions → |
| Salesforce | Medium | View all Salesforce questions → |
| TikTok | Medium | View all TikTok 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.
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.
Sliding window with a count map
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
O(n) timefrom 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 runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Fruit Into Baskets?
Fruit Into Baskets is asked at Amazon, Netflix, Salesforce, TikTok. 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.