Fruit Into Baskets
Problem Statement
You are given an integer array fruits, where fruits[i] is the type of fruit on tree i. Starting from any tree, you must move right one tree at a time and pick exactly one fruit from each tree until you stop. You have two baskets, and each basket can hold only one fruit type. Return the maximum number of fruits you can collect.
Input
An integer array fruits, where each value represents a fruit type along a line of trees.
Output
An integer: the length of the longest contiguous subarray containing at most two distinct fruit types.
Constraints
- •
1 <= fruits.length <= 10^5 - •
0 <= fruits[i] < fruits.length
Examples
Example 1
fruits = [1,2,1]
3Example 2
fruits = [0,1,2,2]
3Example 3
fruits = [1,2,3,2,2]
4Learning Objectives
- Recognise the basket rule as longest subarray with at most two distinct values.
- Maintain a variable window whose frequency map represents the active baskets.
- Shrink from the left only while the distinct-type invariant is violated.
- Use amortised analysis to explain why nested shrink loops still run in O(n).
Intuition
This is a Pattern Identification problem for an at-most-K-distinct variable window, with K = 2. The picked fruits must form one contiguous run because you start somewhere and move only right. The two baskets mean the current run is valid exactly when it contains at most two distinct fruit types.
The feasibility condition is monotone with respect to moving left forward: removing fruits can never create a new distinct type. That gives the standard expand-and-shrink template. Expand right to try a larger run; when a third type appears, shrink left until only two types remain again. Every valid window after shrinking is a candidate answer.
Common mistakes
- ×Treating the problem as choosing any two fruit types globally instead of requiring one contiguous run.
- ×Clearing the whole map when a third type appears rather than shrinking one tree at a time.
- ×Updating the best length before restoring the at-most-two-types invariant.
- ×Forgetting to remove a fruit type from the map when its count becomes zero.
Algorithm Explanation
Window setup
Maintain two pointers left and right, plus a frequency map basketCounts from fruit type to count inside the current window. The invariant after shrinking is basketCounts.size <= 2. Track best as the maximum valid window length seen.
Window visualization
For fruits = [1,2,3,2,2], expand through [1,2] and the map has two types. Adding 3 gives counts 1:1, 2:1, 3:1, which violates the two-basket rule. Shrink from the left by removing 1, leaving [2,3] with counts 2:1, 3:1. Now the window is valid again. Continuing right grows [2,3,2,2], the best length 4.
Algorithm
- Initialise left = 0, best = 0, and an empty frequency map.
- Move right from left to right across fruits.
- Add fruits[right] to the map.
- While the map has more than two distinct fruit types, decrement the count of fruits[left], remove it if the count becomes zero, and increment left.
- After the window is valid, update best with right - left + 1.
- Return best.
Solutions
Solution: Variable window with at most two fruit types
The two baskets are exactly a two-distinct-type constraint. A frequency map tells us how many distinct types are currently inside the window and lets us shrink correctly when a third type appears.
Step-by-step
- Keep left at the start of the current candidate window and store counts in basketCounts.
- For each right, add the new fruit type to the map.
- If the map now contains three types, repeatedly remove fruits[left] and advance left until only two types remain.
- Once valid, compute the current window length.
- Keep the maximum length over the scan.
O(n)
O(1)
Each index enters once and leaves once. The map holds at most three fruit types during repair, so auxiliary space is constant.
Java implementation
Dry Run
Sample input
fruits = [1,2,3,2,2]. Track the current window, basket counts, and best valid length after each right expansion.
| right | fruit | left before shrink | basket counts after add | shrink action | valid window | best |
|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 1:1 | No shrink needed. | 0..0 => [1] | 1 |
| 1 | 2 | 0 | 1:1, 2:1 | No shrink needed. | 0..1 => [1,2] | 2 |
| 2 | 3 | 0 | 1:1, 2:1, 3:1 | Remove fruit 1 at left 0. | 1..2 => [2,3] | 2 |
| 3 | 2 | 1 | 2:2, 3:1 | No shrink needed. | 1..3 => [2,3,2] | 3 |
| 4 | 2 | 1 | 2:3, 3:1 | No shrink needed. | 1..4 => [2,3,2,2] | 4 |
The maximum valid window is indices 1..4, containing [2,3,2,2] with exactly two fruit types and length 4.
Interview Tips
Translate the story into the invariant immediately: longest contiguous subarray with at most two distinct values. Once stated that way, the template is straightforward: expand right, shrink left while distinct types exceed two, then score the valid window. Interviewers often ask about amortised complexity, so mention that each tree is added once and removed at most once.
Likely follow-ups
- How would you generalise this to **k** baskets instead of two?
- How would you return the start and end indices of the best fruit segment?
- What if each basket had a capacity limit as well as a fruit-type restriction?
- How would the answer change if you were allowed to skip trees while moving right?
Similar Problems
Key Takeaways
- Fruit Into Baskets is longest subarray with at most two distinct values.
- A frequency map gives both counts and the current number of distinct types.
- Shrink only while the invariant is broken, then score the restored valid window.
- The expand-shrink loop is linear because both pointers move in one direction.