#904
Fruit Into Baskets
Medium Variable window, at most 2 kinds
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Trees in a row each give one fruit type. With two baskets (one type each), pick from a contiguous stretch of trees. Return the most fruit you can collect.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: longest stretch with at most two kinds of fruit.
Why this works: keep counts per kind in the window; when a third kind enters, shrink from the left until one kind disappears.
Example: [1, 2, 3, 2, 2]
[1, 2] ok, add 3 → three kinds → drop 1[2, 3, 2, 2] → length 4
✦Hints open one at a time
Rephrase: the longest subarray with at most 2 distinct values.
Keep a count per type in the window; shrink when there are 3 types.
↗Approach
Expand right and count types in a map. While the map has more than 2 keys, decrement the left type (removing it at 0) and move left. Track the longest window.
</>Solution (Java)
import java.util.*;
class Solution {
public int totalFruit(int[] fruits) {
Map<Integer, Integer> count = new HashMap<>();
int left = 0, best = 0;
for (int r = 0; r < fruits.length; r++) {
count.merge(fruits[r], 1, Integer::sum);
while (count.size() > 2) {
int f = fruits[left++];
if (count.merge(f, -1, Integer::sum) == 0) count.remove(f); // drop empty baskets
}
best = Math.max(best, r - left + 1);
}
return best;
}
}!Common mistake
Leaving zero-count keys in the map, so map.size() stays too large.
Complexity
- Time: O(n).
- Space: O(1) — at most 3 keys.
Topic: Sliding Window
🎬 Episode 10: video coming soon