Fruit Into Baskets — Longest Subarray with At Most 2 Distinct

Problem Statement#

You walk along a row of trees. Tree i produces fruit of type fruits[i]. You carry exactly two baskets and each basket holds a single fruit type with unlimited quantity. Once you start picking from a tree you cannot skip ahead, but you must stop before adding a third fruit type. Return the maximum number of fruits you can collect.

Constraints:

• 1 <= fruits.length <= 10^5
• 0 <= fruits[i] < fruits.length

Input:  fruits = [1,2,1]
Output: 3

Input:  fruits = [0,1,2,2]
Output: 3

Why This Problem Matters#

LeetCode 904 is the classic "longest subarray with at most K distinct elements" problem disguised as a fruit-picking puzzle, and it shows up at Google, Amazon, Microsoft, and DoorDash. It teaches the canonical shrinkable-window template that powers an entire family of FAANG questions.

The problem is deceptively simple. Many candidates jump to a sliding window without articulating the invariant — "window has at most two distinct types" — and end up with off-by-one bugs around the shrink condition.

After solving it you can immediately solve LC 159 (Longest Substring with At Most Two Distinct Characters) and LC 340 (At Most K Distinct Characters). All three share one template.

The Core Insight#

Maintain a window [l, r] and a HashMap from fruit type to its count inside the window. Expand r one step at a time. Whenever the window contains more than two distinct keys, shrink from the left until you are back to two keys. Track the maximum window length seen.

Each index is added and removed at most once, so the total work is O(n) even though the inner shrink loop is a while. The HashMap stays small — at most three keys at any time before the shrink fires.

The clean way to write the shrink condition is "while map size exceeds 2". It is more readable than counting types manually and works for any K with a single change.

Visual Dry Run#

Trace fruits = [1, 2, 3, 2, 2].

Final answer: 4.

Solution (Optimal)#

class Solution:
    def totalFruit(self, fruits: list[int]) -> int:
        count = {}
        left = 0
        best = 0
 
        for right, f in enumerate(fruits):
            count[f] = count.get(f, 0) + 1
 
            while len(count) > 2:
                lf = fruits[left]
                count[lf] -= 1
                if count[lf] == 0:
                    del count[lf]
                left += 1
 
            best = max(best, right - left + 1)
 
        return best

var totalFruit = function (fruits) {
    const count = new Map();
    let left = 0;
    let best = 0;
 
    for (let right = 0; right < fruits.length; right++) {
        count.set(fruits[right], (count.get(fruits[right]) || 0) + 1);
 
        while (count.size > 2) {
            const lf = fruits[left];
            count.set(lf, count.get(lf) - 1);
            if (count.get(lf) === 0) count.delete(lf);
            left++;
        }
 
        best = Math.max(best, right - left + 1);
    }
 
    return best;
};

Time: O(n) — each index added and removed once. Space: O(1) — at most three keys in the map before the shrink restores it to two.

Common Mistakes#

• Forgetting to delete a key when its count hits zero. The map size check breaks otherwise.
• Using if instead of while for the shrink. After adding one element you might still need to shrink multiple times in degenerate inputs (rare here, common in K-distinct).
• Generalizing to K-distinct without changing the comparison > 2 to > k.
• Tracking maximum length only on the shrink branch instead of every iteration.
• Miscounting types by reading from a stale list rather than the live HashMap.

Interview Tips#

• Recognize the disguise — call it out: "this is longest subarray with at most 2 distinct values".
• Explicitly write the loop invariant as a comment before coding.
• Walk through the example [1, 2, 3, 2, 2] to demonstrate correctness.
• Generalize to K at the end and mention it works in O(n) for any K.
• Sanity-check with a single-type input like [3, 3, 3] — answer is n.

Follow-up Questions#

• Generalize to at most K distinct fruit types. Hint: replace > 2 with > k.
• Find the actual subarray, not just its length. Hint: track left index when best updates.
• What if you have unlimited baskets but each basket holds at most C fruits? Hint: tracking distinct types is no longer enough.
• Variant: at most K replacements allowed. Hint: see LC 424 (Longest Repeating Character Replacement).
• What if the array is streamed? Hint: keep the same map and update on each arrival.

Key Takeaways#

• LeetCode 904 is "longest subarray with at most 2 distinct values" disguised as fruit picking.
• Use a HashMap and a shrinkable sliding window.
• The shrink condition is map.size > 2 — generalizes to K with a one-character change.
• Time O(n), space O(K) where K is the distinct-type cap.
• This template solves LC 159, LC 340, and LC 904 with the same code skeleton.
• Common at Google, Amazon, Microsoft, and DoorDash.
• Always remember to delete map entries when their count drops to zero.