Fruit Into Baskets: Sliding Window with Two Fruit Types

LeetCode 904, Fruit Into Baskets, gives you a row of fruit trees where fruits[i] is the type of fruit at tree i. You have two baskets, and each basket can only hold one type of fruit. Starting at any tree, you pick exactly one fruit from each tree moving right, stopping when you would need to pick a third type. Return the maximum number of fruits you can collect.

Why this problem matters

Fruit Into Baskets is a sliding window problem in disguise. The "story" about baskets and fruit types is really asking: find the longest contiguous subarray that contains at most two distinct values. Once you strip away the narrative, the technique is one of the most reusable patterns in competitive programming and interviews.

Sliding window with a constraint ("at most k distinct elements") appears in dozens of problems. Mastering it here means you can instantly apply the same template to Longest Substring Without Repeating Characters, Minimum Window Substring, and similar questions. The window expands to explore and contracts to restore validity, and your only job is managing when each happens.

This problem also reinforces how a hash map works alongside a window. The map tracks the count of each type inside the current window, and when the number of keys exceeds two, you know it is time to shrink.

The brute force approach

The naive solution checks every possible starting index and walks forward until it encounters a third fruit type:

def total_fruit_brute(fruits):
    n = len(fruits)
    result = 0
    for i in range(n):
        basket = set()
        count = 0
        for j in range(i, n):
            basket.add(fruits[j])
            if len(basket) > 2:
                break
            count += 1
        result = max(result, count)
    return result

This works, but it runs in O(n^2) time because for every starting position, you may scan the rest of the array. For arrays with up to 100,000 elements, that is far too slow.

The key insight

Instead of restarting from every index, maintain a single window defined by two pointers, left and right. Expand right one step at a time. Whenever the window contains more than two fruit types, advance left until only two types remain. The window always represents a valid subarray, and you track the maximum length seen.

Walking through it step by step

The solution

def total_fruit(fruits):
    basket = {}
    left = 0
    result = 0

    for right in range(len(fruits)):
        basket[fruits[right]] = basket.get(fruits[right], 0) + 1

        while len(basket) > 2:
            basket[fruits[left]] -= 1
            if basket[fruits[left]] == 0:
                del basket[fruits[left]]
            left += 1

        result = max(result, right - left + 1)

    return result

The basket dictionary maps each fruit type to its count within the current window. When right advances, you increment the count for the new type. If the dictionary has more than two keys, the while loop shrinks from the left, decrementing counts and deleting keys that drop to zero. After each step, right - left + 1 is the current valid window size, and you keep the running maximum.

Complexity analysis

Each element is added once (when right moves) and removed at most once (when left moves). The hash map never holds more than 3 entries at any moment (briefly 3 before the while loop fires, then back down to 2), so its operations are constant time.

Building blocks

1. Sliding window with a constraint

The core pattern is "expand right, contract left." You always expand one step, check the invariant, then contract until the invariant holds. This template works for any problem that says "at most k distinct" or "at most k violations."

2. Hash map as a frequency counter

The dictionary tracks how many of each fruit type are in the window. When a count hits zero, you remove the key entirely so len(basket) accurately reflects the number of distinct types. This "add on expand, subtract on contract" bookkeeping is the same in Minimum Window Substring and Longest Substring with At Most K Distinct Characters.

Edge cases

• All fruits the same type. The window never contracts. Return n.
• Exactly two types in the entire array. The window expands to cover everything. Return n.
• Every fruit is a different type. The window is always at most size 2. Return 2.
• Single element array. Return 1 immediately.
• Two elements of different types. Both fit in two baskets. Return 2.

Common mistakes

1. Forgetting to delete zero-count keys. If you leave basket[type] = 0 in the dictionary, len(basket) never drops below 3 and the window shrinks to nothing.
2. Using a set instead of a map. A set tells you which types are present but not how many of each. Without counts, you cannot determine when a type is fully removed from the window.
3. Shrinking too aggressively. Some people shrink until only one type remains. You only need to shrink until at most two types remain. The while len(basket) > 2 condition handles this precisely.
4. Off-by-one on window length. The length is right - left + 1, not right - left. Both pointers are inclusive.

From understanding to recall

You can read this explanation and feel like the sliding window approach is obvious. But in an interview, the pressure is different. You need to remember whether the while loop checks > 2 or >= 2. You need to recall that you delete keys at zero, not just decrement them. You need the muscle memory of writing right - left + 1 without second-guessing yourself.

Spaced repetition turns that understanding into recall. The first time you practice, you might need a hint about the hash map cleanup. A few days later, you write the while loop from memory but forget the max update. After a few reps at increasing intervals, the entire template is automatic. You are assembling the pieces, not rederiving the logic.

This problem also pairs well with its siblings. Once you have the "at most 2 distinct" window down, try "at most k distinct" and "exactly k distinct" (using the subtraction trick). Each variant reinforces the same skeleton, building a family of patterns you can deploy instantly.

Related posts

• Longest Substring Without Repeating Characters - Classic sliding window
• Minimum Window Substring - Sliding window with character counting
• Longest Repeating Character Replacement - Window with constraint tracking

The sliding window is one of those patterns where a single clean template covers an enormous range of problems. Nail the expand/contract rhythm here, and you will recognize it instantly when the wording changes but the structure stays the same.