Fruit Into Baskets
Medium · Sliding Window · Array · Hash Table · Sliding Window
Problem
A row of fruit trees is described by fruits, where fruits[i] is the type of fruit on tree i. You carry two baskets, and each basket holds only one type of fruit (but any amount of it).
You pick any starting tree and walk right one tree at a time, taking exactly one fruit from every tree, the first one included. You must stop at the first tree whose fruit fits in neither basket.
Return the largest number of fruits you can collect.
Examples
Input: fruits = [3,3,1,2,2,1,4] Output: 4
Start at index 2 and pick 1, 2, 2, 1; type 4 makes you stop.
Input: fruits = [0,0,0] Output: 3
Only one type grows here, so every tree can be picked.
Input: fruits = [1,2,1,3,3,3,2,2] Output: 5
Start at index 3 and pick 3, 3, 3, 2, 2. Starting at index 2 picks 1, 3, 3, 3 and then stops at the 2.
Constraints
- 1 <= len(fruits) <= 10^5
- 0 <= fruits[i] < len(fruits)
Approaches
- Every start, walk until a third type — time O(n²), space O(1)
Follow-up
With k baskets instead of two, the same window works with len(count) > k as the shrink condition. Can you do two baskets in O(1) memory without a map? Track the last two types and the length of the run of the most recent type: when a third type arrives, the new window is that run plus the new tree.
Related problems
Start free on Cariara · Coding problems · System design studio
