Fruit Into Baskets
Pick the most fruit with two baskets from consecutive trees: the longest sliding window with at most two distinct values.
Problem Understanding
Fruit Into Baskets: trees stand in a row and fruits[i] is the kind of fruit on tree i. You have two baskets, each holding any amount of a single kind. Starting at any tree, you pick one fruit from each tree moving right, and stop when a fruit fits neither basket. Return the most fruit you can pick.
Example: [1, 2, 3, 2, 2] returns 4: start at tree 1 and pick 2, 3, 2, 2.
The Intuition: At Most Two Kinds in the Window
Strip away the story: you want the longest run of consecutive trees with at most two distinct kinds. That is a variable-size sliding window with a count per kind, the same tool as Longest Substring Without Repeating Characters:
- Move
rightforward and countfruits[right]. - If the window now has three kinds, move
leftforward, decreasing counts, until one kind drops to zero and is removed. - Record
right − left + 1.
Each tree enters and leaves the window once, so the whole pass is O(n), and the map never holds more than three kinds.
Interactive Walkthrough
Each cell is a tree labelled with its fruit kind. The shaded window is what the baskets hold, and the panel beside it shows each kind's count. Watch a third kind arrive and push the window forward until one basket empties.
Dry Run Table
Input: [1, 2, 3, 2, 2]
| right | Window | Baskets | Length |
|---|---|---|---|
| 0 | 0..0 | 1×1 | 1 |
| 1 | 0..1 | 1×1, 2×1 | 2 |
| 2 | 1..2 after dropping tree 0 | 2×1, 3×1 | 2 |
| 3 | 1..3 | 2×2, 3×1 | 3 |
| 4 | 1..4 | 2×3, 3×1 | 4 |
The Solution Template
Longest window with at most two distinct values. The C snippet counts kinds in an array, since kinds are below n.
Fruit Into Baskets Code
1var totalFruit = function(fruits) {2 const count = new Map();3 let left = 0, best = 0;4 for (let right = 0; right < fruits.length; right++) {5 count.set(fruits[right], (count.get(fruits[right]) || 0) + 1);6 while (count.size > 2) {7 const f = fruits[left++];8 count.set(f, count.get(f) - 1);9 if (count.get(f) === 0) count.delete(f);10 }11 best = Math.max(best, right - left + 1);12 }13 return best;14};
Edge Cases & Common Mistakes
- Only one or two kinds: the whole row fits; return n.
- Not deleting zero counts: the map size stays too large and the window shrinks too far.
- Resetting the window to the last tree on a third kind: the right restart point is after the last tree of the kind being dropped, not always one tree back.
- Every tree a different kind: the answer is 2 (or 1 for a single tree).
Summary
Two single-kind baskets on consecutive trees means the longest window with at most two distinct values. Count kinds in a map, add on the right, drop from the left until only two kinds remain, and track the longest window. O(n) time, O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet