Fruit Into Baskets — Solution in Python, Java & C++
Fruit Into Baskets solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Fruit Into Baskets is a medium coding problem on arrays, hash table and sliding window.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Sliding Window
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are visiting a row of fruit trees; fruits[i] is the type of fruit the i-th tree produces. You have two baskets, each holding only one type. Starting from any tree and moving right, you pick one fruit per tree until a tree forces a third type.
Return the maximum number of fruits you can pick.
Example 1
Input: fruits = [1,2,1]
Output: 3
Example 2
Input: fruits = [0,1,2,2]
Output: 3
Explanation: Pick from trees [1,2,2].
Example 3
Input: fruits = [1,2,3,2,2]
Output: 4
Explanation: Pick from trees [2,3,2,2].
Constraints
1 <= fruits.length <= 400 <= fruits[i] <= 6
Hints for Fruit Into Baskets
Hint 1
This is 'longest subarray with at most 2 distinct values' in disguise.
Hint 2
Track type counts in the window; shrink while there are 3 distinct types.
How to solve Fruit Into Baskets
Strip away the story and this is "longest contiguous subarray containing at most two distinct values". Two baskets means two allowed types; picking until a third appears means the window must stay within that limit. Slide a window, keeping a count per type, and shrink whenever a third type sneaks in.
Approach
- Keep a frequency table for the types inside the window plus a count of how many distinct types it holds.
- Advance the right edge; if the incoming type was absent, the distinct count grows.
- While the distinct count exceeds two, advance the left edge, decrementing that type's frequency and lowering the distinct count when it hits zero.
- Record the window length once the invariant holds again.
- The largest such window is the answer.
Why it works
Every valid picking run is a contiguous block with at most two types, and every such block is a valid run — so the two maxima coincide. The window only shrinks to restore the invariant, never speculatively, so for each right edge it holds the longest valid block ending there; taking the maximum over all right edges covers every candidate. Each index enters and leaves once, keeping it linear despite the inner loop.
Complexity
- Time —
O(n) - Space —
O(1) — at most three types are ever tracked
Pitfalls
- Decrement the distinct count only when a type's frequency actually reaches zero, not on every removal.
- Measure the window after restoring the invariant, or you count runs that need three baskets.
- You may start at any tree, which is exactly what makes this a subarray problem rather than a prefix one.
- Fewer than two distinct types in the whole array is fine — the answer is then the entire array.
Reference solution
Python
from typing import List
def totalFruit(fruits: List[int]) -> int:
count = {}
l = 0
best = 0
for r, f in enumerate(fruits):
count[f] = count.get(f, 0) + 1
while len(count) > 2:
g = fruits[l]
count[g] -= 1
if count[g] == 0:
del count[g]
l += 1
best = max(best, r - l + 1)
return bestJava
public static int totalFruit(int[] fruits) {
int[] count = new int[64];
int distinct = 0, l = 0, best = 0;
for (int r = 0; r < fruits.length; r++) {
if (count[fruits[r]] == 0) distinct++;
count[fruits[r]]++;
while (distinct > 2) {
count[fruits[l]]--;
if (count[fruits[l]] == 0) distinct--;
l++;
}
if (r - l + 1 > best) best = r - l + 1;
}
return best;
}C++
int totalFruit(vector<int>& fruits) {
vector<int> count(64, 0);
int distinct = 0, l = 0, best = 0;
for (int r = 0; r < (int) fruits.size(); r++) {
if (count[fruits[r]] == 0) distinct++;
count[fruits[r]]++;
while (distinct > 2) {
count[fruits[l]]--;
if (count[fruits[l]] == 0) distinct--;
l++;
}
if (r - l + 1 > best) best = r - l + 1;
}
return best;
}JavaScript
var totalFruit = function(fruits) {
const count = new Map();
let l = 0, best = 0;
for (let r = 0; r < fruits.length; r++) {
count.set(fruits[r], (count.get(fruits[r]) || 0) + 1);
while (count.size > 2) {
const f = fruits[l];
count.set(f, count.get(f) - 1);
if (count.get(f) === 0) count.delete(f);
l++;
}
best = Math.max(best, r - l + 1);
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets