Fruit Into Baskets
You have two baskets, each holding only one type of fruit. Starting at any tree you must pick from every tree moving right until you cannot. Return the maximum number of fruits you can collect.
- 1 <= fruits.length <= 10⁵
- 0 <= fruits[i] < fruits.length
Intuition
Fruit into baskets is worded as picking fruit into two baskets, each holding one type, from a contiguous run of trees. Stripped of the framing:
- Find the longest subarray containing at most two distinct values.
Recognising that is most of the work, and it makes the problem a direct instance of Longest Substring with At Most K Distinct Characters, with k = 2.
A sliding window solves it. Extend the right edge, adding each fruit type to a count map. When the map holds more than two types, shrink from the left until it holds two again, and record the window length at each step.
The shrinking step is where correctness lives. A type is removed from the map only when its count reaches zero, not on the first decrement — a window like [1, 2, 1] contains two 1s, and dropping the type after removing the first would wrongly report only one distinct type remaining.
The window never shrinks below two distinct types, so the left pointer only moves forward. Each element enters and leaves the window at most once, keeping the whole scan linear despite the nested loop.
The answer is the maximum window length seen, and the maximum must be recorded after the shrink, when the window is valid again.
Generalising k = 2 to arbitrary k changes nothing but the comparison, which is worth noticing — the same code solves the general problem.
Stripped of its story, this is "longest subarray with at most 2 distinct values". The two baskets are a hash map capped at size 2. Once you see the translation, the generic k-distinct window solves it with k = 2 and no further thought.
Approach
Before reading on: price up what the direct approach costs here, then ask what makes a window invalid, and which pointer should move when it is. Aim for O(n) time and O(1) space.
Translate the wording
Two baskets each holding one fruit type, over consecutive trees, means: the longest subarray with at most two distinct values. Recognising this is most of the problem.
Extend the window right
Move the right edge forward, incrementing each fruit type's count in a map. The map size is the number of distinct types currently in the window.
Shrink when a third type appears
While the map holds more than two types, decrement the leftmost fruit's count and advance the left pointer until only two remain.
Remove a type only at zero
Delete a type from the map only when its count reaches 0, not on the first decrement. A window like [1, 2, 1] holds two 1s, and removing early undercounts the distinct types.
Record after shrinking
Update the maximum length once the window is valid again. Measuring mid-shrink records an invalid window.
Note the linear cost
The left pointer only moves forward, so each element enters and leaves once. The nested loop does not make this quadratic.
Cost of the scan
Each element is visited at most twice, giving O(n) time, with O(1) space since the map never exceeds three entries.
Solution & live demo
Common pitfalls
Leaving zero-count keys in the map
count[fruits[left]] -= 1 left += 1
count[fruits[left]] -= 1
if count[fruits[left]] == 0:
del count[fruits[left]]
left += 1len(count) is the validity test, so a key sitting at zero still inflates the size. The window then shrinks further than needed and the reported answer is too short.
Shrinking to at most 2 total fruits rather than 2 types
while right - left + 1 > 2:
while len(count) > 2:
The baskets hold unlimited fruit of two types, not two pieces. Bounding the window length instead of the distinct count caps every answer at 2.
Resetting the window on a violation
if len(count) > 2:
count = {}
left = rightwhile len(count) > 2:
...
left += 1Restarting throws away the valid suffix that could extend the next window — after a violation, the trailing run of the newest fruit is still usable. Incremental shrinking preserves it and keeps the whole scan linear.
Edge cases
The window never shrinks and the answer is the whole array length.
The window never exceeds length 2, which is the correct answer.
The answer is 1.
The window correctly spans across the break as long as only two types are present, which is why a naive 'longest run of one type' scan gets this wrong.