Fruit Into Baskets

You are walking along a row of fruit trees; fruits[i] is the type of fruit tree i. You have two baskets, each of which can hold only a single type of fruit (but any amount). Starting from any tree, you pick exactly one fruit from every tree, moving right, and must stop as soon as you'd need a third basket.

Return the maximum number of fruits you can pick — i.e. the length of the longest contiguous subarray containing at most two distinct values.

Hints

· Stuck? Reveal one nudge at a time.

Two baskets that each hold one type — what does that limit about your picked run?

It's the longest contiguous subarray with at most two distinct values.

Slide a window with a count map; when a third type enters, shrink from the left.

Common doubts

You need to know when a type fully leaves the window as you shrink. Counting occurrences lets you delete a type exactly when its count hits zero.

It's the number of keys in the map. Growing may push it to three; shrinking brings it back to two.

No — the sliding window implicitly considers every start; you only ever move both pointers forward.

Interview follow-ups

· What an interviewer asks next.

Identical template with the condition 'map size > k' — that's the next problem, Longest Substring with At Most K Distinct.

When you update the best length, snapshot the current map's keys (there are at most two).

Fun facts

Fruit Into Baskets is just 'at most 2 distinct' dressed up — recognizing the disguise is half the interview.
The count-map-size-as-distinct-count trick generalizes directly to any 'at most k distinct' window.

Asked at

GoogleAmazonMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: fruits = [1,2,1]
Output: 3
Only two types (1 and 2), so all three fruits can be picked.

Example 2

Input: fruits = [1,2,3,2,2]
Output: 4
Pick [2,3,2,2] — two types — for four fruits.

Constraints

- 1 <= fruits.length <= 10^5 - 0 <= fruits[i] < fruits.length

Strip away the fruit story and it's a clean window question: the longest contiguous subarray with at most two distinct values. Grow the window on the right; whenever it holds a third type, shrink from the left until only two remain.

Prerequisites

Before you start

· Concepts used directly in the solution.

Variable window. Growing and shrinking a window to keep a condition true.

Count map. A hash map of value -> occurrences inside the window, so you know how many distinct types it holds.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

The rules

“What does 'two baskets' translate to?”

At most two distinct fruit types in your picked run.

“Do I pick a contiguous run?”

Yes — you move right tree by tree, so the picked fruits form a contiguous subarray.

The ideal opening — say it like this

Two baskets means at most two distinct fruit types, so this is the longest subarray with <= 2 distinct values.

I keep a count map of the types in the window and extend the right edge.

When a third type appears, I shrink from the left until one type drops out, and track the longest width.

Understand the problem

Worked example — fruits = [1, 2, 3, 2, 2]

right=0 {1}        window [1]        best 1
right=1 {1,2}      window [1,2]      best 2
right=2 {1,2,3}!   shrink -> {2,3}   window [2,3]  best 2
right=3 {2,3}      window [2,3,2]    best 3
right=4 {2,3}      window [2,3,2,2]  best 4
answer: 4

Key observations

1Aha

Two baskets = at most two distinct values

The fruit types are just labels; the only constraint is that the window contains no more than two of them.

2Aha

The count map is the distinct counter

The number of keys in the map is exactly the number of distinct types in the window. Deleting a key when its count reaches zero keeps that accurate.

3Aha

Shrink only when a third type enters

Grow greedily; contract from the left exactly when a third type appears, and only until it's gone. Both pointers move forward, so O(n).

Brute force vs optimal

	Extend from each start	Sliding window
Idea	From each index, extend while <= 2 distinct	One window, shrink when a third type enters
Time	O(n^2)	O(n)
Space	O(1)	O(1)

The brute rebuilds the type set from each index; the window carries a count map forward, only moving both pointers right. Full code is in the Approaches selector below.

Summary

Key takeaway

"Two baskets" is "at most two distinct values". Grow the window on the right with a count map; when a third type appears, shrink from the left until it's gone, tracking the longest width. One O(n) pass with O(1) extra space (at most three map entries).

count = {}; left = 0; best = 0
for right in 0 .. n-1:
    count[fruits[right]] += 1
    while len(count) > 2: count[fruits[left]] -= 1; drop if 0; left += 1
    best = max(best, right - left + 1)
return best