NeetCode #234LC-904MediumSliding Window
← Back to All Problems#234 · #904 · Fruit Into Baskets(水果成篮)
📌 Problem Statement & Constraints
You are given an array
fruits where fruits[i] is the type of fruit on tree i. You have two baskets, each of which can hold only one type of fruit (but unlimited quantity). Starting from any tree, you must pick exactly one fruit from every tree while moving right, stopping when you cannot continue. Return the maximum number of fruits you can pick. Constraints: 1 <= fruits.length <= 10^5, 0 <= fruits[i] < fruits.length.💡 Core Algorithmic Approaches
- This is exactly Longest Substring with At Most Two Distinct Characters, with fruit types playing the role of characters.
- Maintain a window with at most two distinct fruit types using a frequency map.
- Shrink from the left whenever a third type enters, deleting keys whose count reaches zero.
- The window length is the candidate answer.
💻 Benchmark Python3 Implementation
class Solution:
def totalFruit(self, fruits: List[int]) -> int:
from collections import defaultdict
cnt = defaultdict(int)
l = 0
best = 0
for r, f in enumerate(fruits):
cnt[f] += 1
while len(cnt) > 2: # a third type entered
cnt[fruits[l]] -= 1
if cnt[fruits[l]] == 0:
del cnt[fruits[l]]
l += 1
best = max(best, r - l + 1)
return best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each tree enters and leaves the window at most once.
💾 Space Complexity
O(1): the map holds at most 3 entries.
⚠️ Interview Pitfalls & Follow-ups
- Not deleting zero-count keys:
len(cnt)would overcount the types and the window would shrink too far. - Using a set instead of a count map: a set cannot track multiplicities, so the shrink loop would remove a type prematurely.
- Assuming the two baskets must hold different types: they may hold the same type, which the general window handles.
- Restarting the window from scratch on a third type: the optimal window may start anywhere, so shrinking is correct.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Sliding Window Problems
#219 · #219Contains Duplicate II#220 · #121Best Time to Buy and Sell Stock#221 · #2379Minimum Recolors to Get K Consecutive Black Blocks#222 · #1984Minimum Difference Between Highest and Lowest of K Scores#223 · #1343Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold#224 · #1052Grumpy Bookstore Owner