Fruit Into Baskets: At Most Two Distinct, Decoded

"Fruit Into Baskets" shows up again and again in Google, Amazon, Walmart phone screens. It is a Medium problem on paper, but the real test is whether you recognize the Sliding Window pattern quickly and code it cleanly. Part 7 of 11 in the Sliding Window arc.

The Problem

You walk a row of fruit trees, fruits[i] being the fruit type at tree i. You have two baskets, each holding one type only, and you pick one fruit per tree moving right from wherever you start; you must stop at the first tree that fits neither basket. Return the maximum number of fruits you can pick. Strip the story and this is: longest contiguous subarray containing at most two distinct values.

Input:  fruits = [1, 2, 3, 2, 2]
Output: 4
Pick trees [2, 3, 2, 2] — two types, four fruits.

Recognizing the Sliding Window Pattern

Sliding window maintains a contiguous range over an array or string and slides its boundaries instead of recomputing from scratch. Fixed-size windows update a running aggregate in O(1) per step; variable-size windows grow the right edge and shrink the left only when a constraint breaks. Any problem asking about the best contiguous subarray or substring under a constraint should trigger this pattern.

Half the difficulty is translation: Google deliberately wraps a standard window problem in narrative. Once decoded — longest window, at-most-2-distinct constraint — the counts-map template applies verbatim.

The Approach

Maintain a type-to-count map. Grow right; when the map exceeds two types, shrink from the left, decrementing counts and deleting zeroed types, until only two remain. Track the best window length throughout.

Write it with k as a parameter and pass k=2 — the interviewer's follow-up is almost always the generalization, and you will have pre-answered it.

Python Solution

def total_fruit(fruits: list[int]) -> int:
    """Longest window containing at most two distinct values."""
    return longest_k_distinct(fruits, 2)


def longest_k_distinct(values: list[int], k: int) -> int:
    counts: dict[int, int] = {}
    left = 0
    best = 0
    for right, v in enumerate(values):
        counts[v] = counts.get(v, 0) + 1
        while len(counts) > k:
            u = values[left]
            counts[u] -= 1
            if counts[u] == 0:
                del counts[u]
            left += 1
        best = max(best, right - left + 1)
    return best

Complexity

• Time: O(n) — each element enters and leaves the window at most once
• Space: O(k) — the counts map holds at most k + 1 types

Interview Tips and Follow-Ups

• Practice the decode step: restate the story as a formal constraint before coding. Interviewers grade the restatement.
• The generalized k-distinct version is LeetCode 340 (premium) and a genuine Google follow-up — you already wrote it.
• Edge case: fewer than k distinct types overall means the whole array is the answer; confirm your loop handles it naturally.

That wraps part 7 of the Sliding Window arc. The full Technical Interview category maps all one hundred questions to the nine patterns that dominate FAANG screens — work through an arc end to end and the next unseen variant will feel familiar.