⚡Flashcard Drill➔
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

  1. This is exactly Longest Substring with At Most Two Distinct Characters, with fruit types playing the role of characters.
  2. Maintain a window with at most two distinct fruit types using a frequency map.
  3. Shrink from the left whenever a third type enters, deleting keys whose count reaches zero.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Sliding Window Problems