LeetCode #904 Medium

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.

sliding-windowarrayhashing

Open on LeetCode ↗

02

Intuition

Strip away the story and the constraint is: find the longest contiguous subarray containing at most two distinct values. Two baskets means two types; picking from consecutive trees means a contiguous window. That reframing is most of the work — once stated this way it is the standard 'at most k distinct' sliding window with k = 2.

How to spot this pattern

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.

03

Approach

1

Translate the problem statement

Each basket holds one fruit type, so a valid picking run uses at most two distinct types. Picking must proceed from consecutive trees, so the run is contiguous. Maximising the fruit collected is maximising the length of that run. The answer is therefore the longest subarray with at most two distinct elements — a formulation with a well-known solution.

2

Maintain a count map over the window

Slide a window with a hash map from fruit type to its count inside the window. Advancing the right edge adds a fruit and may introduce a new type. The window is valid while the map holds at most two keys.

3

Shrink when a third type appears

If adding a fruit brings the distinct count to three, advance the left edge, decrementing counts and deleting keys that reach zero, until only two types remain. Record the window length after every step. Both pointers move only forward, giving O(n) time and O(1) space since the map never exceeds three entries. Generalising the constant 2 to a parameter k solves 'Longest Substring with At Most K Distinct Characters' with no other change.

04

Solution & live demo

▶1class Solution:
▶2    def totalFruit(self, fruits):
▶3        count = {}
▶4        left = best = 0
▶5        for right, f in enumerate(fruits):
▶6            count[f] = count.get(f, 0) + 1
▶7            while len(count) > 2:
▶8                count[fruits[left]] -= 1
▶9                if count[fruits[left]] == 0:
▶10                    del count[fruits[left]]
▶11                left += 1
▶12            best = max(best, right - left + 1)
▶13        return best

05

Common pitfalls

Leaving zero-count keys in the map

✗ Wrong

count[fruits[left]] -= 1
left += 1

✓ Right

count[fruits[left]] -= 1
if count[fruits[left]] == 0:
    del count[fruits[left]]
left += 1

len(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

✗ Wrong

while right - left + 1 > 2:

✓ Right

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

✗ Wrong

if len(count) > 2:
    count = {}
    left = right

✓ Right

while len(count) > 2:
    ...
    left += 1

Restarting 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.

06

Edge cases

One or two distinct types overall

The window never shrinks and the answer is the whole array length.

Every tree a different type

The window never exceeds length 2, which is the correct answer.

Single tree

The answer is 1.

Long run of one type broken by a single other

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.

07

Complexity

Time

O(n)

Space

O(1)

The map holds at most three keys at any moment. Each pointer advances at most n times.