Sliding Window Pattern

Fruit Into Baskets

You are visiting a farm that has a single row of fruit trees arranged in some order represented by an integer array fruits. You want to collect as much fruit as possible. However, the owner has some strict rules: you only have two baskets, and each basket can only hold a single type of fruit. There is no limit on the amount of fruit each basket can hold. Starting from any tree you choose, you must pick exactly one fruit from every tree (including the start tree) while moving to the right. You must stop if you would have to put a third type of fruit in a basket. Given the integer array fruits, return the maximum number of fruits you can pick.

CONSTRAINTS

1 <= fruits.length <= 10⁵
0 <= fruits[i] < fruits.length

EXAMPLE 1

Input: fruits = [1,2,1]

Output: 3

We can collect all three fruits [1,2,1] — they use only 2 distinct types (1 and 2). Use the entire array.

EXAMPLE 2

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

Output: 3

Best window is [1,2,2] (length 3) using types 1 and 2. Starting from 0 would introduce 3 types.

EXAMPLE 3

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

Output: 4

Best window is [2,3,2,2] (length 4) using types 2 and 3. The leading 1 is excluded.

How many baskets do I have?

Exactly two. Each basket holds one type of fruit. So the window can contain at most 2 distinct fruit types.

Do I have to start from the beginning of the array?

No. You can start from any tree. You are looking for the longest contiguous subarray with at most 2 distinct types.

Must the fruits be from consecutive trees (no skipping)?

Yes. You collect from consecutive trees — you cannot skip. This is why it maps to a contiguous subarray problem.

Can both baskets hold the same type?

Yes. Having only 1 distinct type is a valid state — 'at most 2' includes 1.

Strip away the orchard story and the problem is bare: you pick from consecutive trees and must stop before a third kind of fruit appears, so you want the longest contiguous window containing at most 2 distinct values. "Two baskets, one type each" is just a cap of 2 on how many distinct numbers the window may hold.

That is once again the longest-window Variable Sliding Window, the same shape as Max Consecutive Ones III. The only thing swapped is the rule for "invalid": there it was "more than k zeros"; here it is "more than 2 distinct kinds". In fact this is the general at-most-k-distinct template with k fixed at 2 — remember that, because the same code with a parameter solves a whole class of problems.

Why not brute force

Restarting a distinct-count from every tree is O(N²), re-walking overlapping stretches. The window reuses that overlap.

Expand, and evict a whole kind when a third appears

Keep a small tally: how many of each fruit type sit in the window (its number of keys = how many distinct kinds). Extend right and add the new fruit. While the tally has more than 2 keys, walk left forward, decrementing kinds as they leave, and delete a key when its count hits 0 — that deletion is what actually drops the distinct-count back to 2. Then measure the width.

python

def totalFruit(fruits):
    count = {}
    left = 0
    best = 0
    for right in range(len(fruits)):
        count[fruits[right]] = count.get(fruits[right], 0) + 1
        while len(count) > 2:              # a 3rd kind appeared - evict from the left
            f = fruits[left]
            count[f] -= 1
            if count[f] == 0:
                del count[f]               # this is what lowers the distinct-count
            left += 1
        best = max(best, right - left + 1)
    return best

Crucial Notethe distinct-count is len(count), so a leftover {type: 0} entry would keep counting a fruit that is really gone from the window. Deleting the key at zero is not tidiness — it is how the window learns it is back to two kinds.

Worked Example:fruits = [1, 2, 3, 2, 2]
- right=0 type1: {1:1}. width 1, best 1.
- right=1 type2: {1:1, 2:1}. width 2, best 2.
- right=2 type3: {1:1, 2:1, 3:1} — 3 kinds, evict: drop type1, {2:1, 3:1}, left=1. width 2.
- right=3 type2: {2:2, 3:1}. width 3, best 3.
- right=4 type2: {2:3, 3:1}. width 4, best 4.
- Answer: 4 (the stretch [2,3,2,2]).

How it maps onto the pattern

The four slots: (a) invalid = more than 2 distinct kinds (len(count) > 2); (b) expand adds one to a kind's tally; (c) shrinking decrements a kind and deletes it at zero; (d) record = max width. Recognise it whenever a problem caps the variety inside a contiguous stretch — "at most two types", "at most k distinct", "no more than k different" — and asks for the longest such stretch. Bump the 2 to a k and this exact code is the reusable helper you will call twice in Subarrays with K Different Integers.

Interactive Strategy Visualization