Fruit Into Baskets

Hit this on a Bloomberg onsite, last round, and the framing tripped me up. The interviewer narrated a story about a farmer with two baskets walking down a row of fruit trees, and I burned three minutes mapping the words to indices. Once you see past the costume, it is the canonical longest-window-with-at-most-2-distinct problem, and the same template generalizes to K distinct.

Fruit Into Baskets

You are visiting a farm of fruit trees laid out in a single row. The farm is given as an integer array fruits where fruits[i] is the type of fruit on the i-th tree.

You have two baskets. Each basket can hold any quantity of fruit, but each basket can hold only one type of fruit. Starting from any tree, you must pick exactly one fruit from every tree (including the start tree) while moving to the right. You stop the moment you reach a tree whose fruit cannot fit in either basket.

Return the maximum number of fruits you can pick.

Examples

Example 1:

• Input: fruits = [1, 2, 1]
• Output: 3
• Explanation: Pick from all three trees. The two baskets hold types 1 and 2.

Example 2:

• Input: fruits = [0, 1, 2, 2]
• Output: 3
• Explanation: Start at index 1, pick types 1 and 2 across trees 1, 2, 3. Starting at index 0 only yields 2 because the third tree introduces a third fruit type.

Example 3:

• Input: fruits = [1, 2, 3, 2, 2]
• Output: 4
• Explanation: Start at index 1, pick types 2 and 3 across trees 1 through 4.

Example 4:

• Input: fruits = [3, 3, 3, 1, 2, 1, 1, 2, 3, 3, 4]
• Output: 5
• Explanation: The longest window with at most two types is [1, 2, 1, 1, 2] (indices 3..7).

Constraints

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

Follow-up

How would the algorithm change if you had K baskets instead of 2? (The same sliding window with a count map handles general K, with the inner shrink loop running while map.size > K.)