Problem Overview
LeetCode 904 — Fruit Into Baskets — gives you an integer array fruits where fruits[i] is the type of fruit at tree i. You have two baskets, each of which can hold only one type of fruit but unlimited quantity. Starting from any tree, you pick fruits moving right, stopping when you encounter a third type. Return the maximum number of fruits you can collect.
Rephrased as an algorithm problem: find the length of the longest contiguous subarray containing at most 2 distinct values. This is a direct application of the sliding window technique with a hash map tracking element frequencies.
The sliding window approach maintains a window [left, right] that always contains at most 2 distinct fruit types. When adding fruits[right] introduces a third type, shrink from the left until the window is valid again. Track the maximum window length throughout.
- Input: array fruits[] of integer fruit types
- Two baskets, each holds exactly one fruit type
- Pick consecutive fruits starting from any tree
- Stop when encountering a third distinct type
- Return maximum number of fruits collectible
Sliding Window with Hash Map
Initialize left = 0, maxLen = 0, and an empty hash map count that maps fruit type to its frequency within the current window. Iterate right from 0 to n-1, adding fruits[right] to the map by incrementing its count.
After adding the new fruit, check if the map has more than 2 keys. If so, the window is invalid. Shrink from the left: decrement count[fruits[left]], and if it reaches 0, delete the key from the map. Increment left. Repeat until the map has at most 2 keys.
After the window is valid, update maxLen = max(maxLen, right - left + 1). This captures the longest valid window seen so far. The right pointer never moves backward, and the left pointer only moves forward, so each element is processed at most twice.
Delete Zero-Count Keys
When a fruit type's count drops to 0, remove it from the hash map entirely. The map size check (> 2 keys) relies on each key having a positive count. Leaving zero-count keys inflates the key count and breaks the algorithm.
Step-by-Step Walkthrough
Consider fruits = [1, 2, 1, 2, 3, 3, 2]. Start with left=0, maxLen=0, count={}. Right=0: add 1 → count={1:1}, 1 type, maxLen=1. Right=1: add 2 → count={1:1, 2:1}, 2 types, maxLen=2. Right=2: add 1 → count={1:2, 2:1}, 2 types, maxLen=3.
Right=3: add 2 → count={1:2, 2:2}, 2 types, maxLen=4. Right=4: add 3 → count={1:2, 2:2, 3:1}, 3 types — invalid! Shrink: remove fruits[0]=1 → count={1:1, 2:2, 3:1}, still 3. Remove fruits[1]=2 → count={1:1, 2:1, 3:1}, still 3. Remove fruits[2]=1 → count={2:1, 3:1}, now 2 types. left=3, maxLen stays 4.
Right=5: add 3 → count={2:1, 3:2}, 2 types, window=3 (indices 3-5), maxLen=4. Right=6: add 2 → count={2:2, 3:2}, 2 types, window=4 (indices 3-6), maxLen=4. Final answer: 4 (the subarray [1,2,1,2] or [2,3,3,2]).
Generalization to K Distinct Elements
Fruit Into Baskets is a special case of Longest Substring with At Most K Distinct Characters (LeetCode 340) where K=2 and the input is an integer array instead of a string. The algorithm is identical — just replace the constraint from 2 to K.
The generalized version uses the same sliding window with hash map. The only change is the validity check: instead of map.size > 2, check map.size > K. This makes the algorithm a reusable template for any K-distinct constraint problem.
Understanding this generalization is valuable in interviews. When you see Fruit Into Baskets, immediately recognize it as K=2 distinct elements. State this connection to the interviewer — it shows pattern recognition and the ability to relate specific problems to general templates.
The K-Distinct Template
Many sliding window problems reduce to "longest subarray with at most K distinct elements." Fruit Into Baskets (K=2), Longest Substring Without Repeating Characters (K=unique count), and Subarrays with K Different Integers (exactly K) all share this core.
Implementation in Python and Java
In Python, use collections.defaultdict(int) for the count map. The shrink loop is while len(count) > 2. When decrementing, use if count[fruits[left]] == 0: del count[fruits[left]] to remove zero entries. The entire solution is about 15 lines.
In Java, use a HashMap<Integer, Integer>. The pattern is identical. Use map.getOrDefault(type, 0) + 1 to increment, and map.remove(type) when the count reaches 0. The while loop shrinks until map.size() <= 2.
An alternative approach avoids the hash map entirely for the K=2 case: track the last two fruit types and the index where the current run started. When a third type appears, set left to the start of the previous type's last contiguous run. This runs in O(1) space but is harder to generalize.
Complexity Analysis
Time complexity is O(n). The right pointer moves from 0 to n-1 (n steps). The left pointer also moves at most n steps total across all iterations. Each element is added to and removed from the map at most once. Total operations: 2n.
Space complexity is O(1) for the hash map. The map holds at most 3 entries (momentarily during the shrink phase). For the general K-distinct case, the map holds at most K+1 entries, which is O(K). When K is constant (as here with K=2), space is O(1).
This is optimal — any algorithm must read every element at least once, giving an O(n) lower bound. The sliding window achieves this with no redundant work and minimal auxiliary space.
YeetCode Flashcard Tip
Fruit Into Baskets is the perfect entry point for sliding window problems. Practice it alongside Longest Substring Without Repeating Characters and Minimum Window Substring on YeetCode to master the expand-shrink pattern.