Fruit Into Baskets
Problem statement
You're walking along a row of fruit trees. Each tree produces one type of
fruit, given as fruits[i], an integer id for that type. You carry exactly
two baskets, and each basket can hold only one fruit type — but as much of it
as you like.
Starting from any tree you choose, you must pick exactly one fruit from every tree as you move to the right, without skipping any. You stop the moment you reach a tree whose fruit type doesn't fit in either basket.
Return the largest number of fruits you can collect this way. Because you can't skip a tree, the trees you visit always form one unbroken stretch — so this is really asking: what's the longest contiguous stretch of trees that contains at most 2 distinct fruit types?
Examples
Example 1
Input: fruits = [1,2,1]
Output: 3
Explanation: All 3 trees use only two fruit types (1 and 2), so you
Example 2
Input: fruits = [0,1,2,2]
Output: 3
Explanation: Starting from index 1 gives [1,2,2], which uses only types
Example 3
Input: fruits = [1,2,3,2,2]
Output: 4
Explanation: Starting from index 1 gives [2,3,2,2], which uses only
Hints
Approach
Optimal: Track each type's last-seen index, jump instead of shrinking
Intuition
The Better approach's shrink loop can take several steps in a row, because it only removes one tree at a time and has to wait for a type's count to hit zero. There's a shortcut: instead of counting how many of each type are in the window, just remember the last index where each type was seen. The moment a 3rd type shows up, you already know exactly which type to drop — the one that hasn't been seen in the longest time — and exactly where the new window should start: right after that type's last occurrence. No loop is needed, because everything before that index is guaranteed to belong only to the type being dropped or to something even older, so nothing valid is skipped.
This is what makes it faster in practice than the Better approach: every step does one lookup and, at most, one direct jump — never a run of several shrink steps in a row.
Steps
- Start with
left = 0, an empty maplast_seen(fruit type → its most recent index), andbest = 0. - For each
rightfrom0ton - 1:- Record
last_seen[fruits[right]] = right. - If
last_seennow holds more than 2 distinct types:- Find the type whose last-seen index is smallest (the one used longest ago).
- Set
leftto one past that index. - Remove that type from
last_seen.
- Update
bestwithright - left + 1.
- Record
- Return
best.
Dry run
fruits = [1, 2, 3, 2, 2]
| right | fruit | last_seen after recording |
evicted type (oldest) | new left |
window size | best |
|---|---|---|---|---|---|---|
| 0 | 1 | {1: 0} |
— | 0 | 1 | 1 |
| 1 | 2 | {1: 0, 2: 1} |
— | 0 | 2 | 2 |
| 2 | 3 | {1: 0, 2: 1, 3: 2} |
1 (last seen at 0) |
1 | 2 | 2 |
| 3 | 2 | {2: 3, 3: 2} |
— | 1 | 3 | 3 |
| 4 | 2 | {2: 4, 3: 2} |
— | 1 | 4 | 4 |
The window ends up covering indices 1..4, exactly [2, 3, 2, 2] — matching
the example's explanation.
Edge cases: a single-tree row returns 1 immediately, since last_seen never
exceeds one entry. A row using only one or two fruit types in total never
triggers an eviction, so left stays at 0 the whole way and the answer is
the full length of the row.
Complexity
Time O(n) - each tree is looked at exactly once. Instead of a variable number of shrink steps, an overflowing window is fixed with a single direct jump, checked against at most 3 stored entries — a constant amount of work per tree.
Space O(1) - the map holds at most 3 entries (fruit type → its last-seen index) at any moment.
class Solution:
def totalFruit(self, fruits: list[int]) -> int:
last_seen: dict[int, int] = {}
left = 0
best = 0
for right, fruit in enumerate(fruits):
last_seen[fruit] = right
if len(last_seen) > 2:
evict_type = min(last_seen, key=last_seen.get)
left = last_seen[evict_type] + 1
del last_seen[evict_type]
best = max(best, right - left + 1)
return best
if __name__ == "__main__":
print(Solution().totalFruit([1, 2, 1])) # 3
print(Solution().totalFruit([0, 1, 2, 2])) # 3
print(Solution().totalFruit([1, 2, 3, 2, 2])) # 4RecapThe whole problem in a few lines, for the night before
- Spot it: longest subarray with at most 2 distinct values
- Idea: variable window with a small count map; when a third type enters, move the left edge until only two types remain
- Cost: O(n) time, O(1) space (at most 3 keys)
- Trap: delete a key from the map when its count drops to zero, or the distinct count will be wrong
Interview follow-ups
What if there were
kbaskets instead of exactly 2?Change every
> 2check to> kin either approach — the algorithm and its O(n) time complexity don't otherwise change. The map can now briefly hold up tok + 1entries instead of 3, so space becomes O(k) instead of O(1).Return the actual range of tree indices for the best window, not just its length.
Track
bestLeftandbestRightalongsidebest, and update all three together whenever a new best window is found:bestLeft = left,bestRight = right. At the end, the best stretch of trees isfruits[bestLeft : bestRight + 1].The row of trees streams in and doesn't fit in memory. How would you adapt this?
Both sliding-window approaches already process one tree at a time and only ever keep a small map alongside the two pointers — nothing about them requires the whole row up front. Feed trees in one at a time exactly as they arrive; memory stays O(distinct types in the window), which is at most 3, regardless of how long the stream runs.
Frequently asked questions
The basket rule says only 2 fruit types can be carried at once, and the "pick from every tree, don't skip" rule means the trees you visit always form one unbroken stretch. Put those two rules together and you get exactly this: find the longest contiguous stretch of the array that uses at most 2 distinct values.
Everything at or before the evicted type's last-seen index belongs either to that type itself or to something even older that's no longer relevant — the two types you're keeping both have their most recent occurrence after that index, by definition of "oldest last-seen index" being the one chosen for eviction. So nothing that still matters gets skipped, and no valid, longer window could have started any earlier than that.
The same shape shows up when scanning a stream of events for the longest stretch that only touches a small number of things at once — for example, the longest run of consecutive log lines that mention at most two service names, or the longest window of a canary rollout during which traffic only ever hit two versions of a feature flag.
Both approaches generalize directly: replace "more than 2 distinct types" with
"more than k distinct types" everywhere. The frequency-map approach's shrink
loop and the last-seen approach's eviction step both work exactly the same
way, just compared against k instead of a fixed 2.
