Fruit Into Baskets

mediumSliding Window30 stepsJava · Python · C++

You have two baskets, each holding one fruit type. Find the longest contiguous stretch with at most two distinct types. Count types inside the window with a map; when a third type enters, shrink from the left until one type disappears.

▶ Watch the animated trace

Traced input: fruits = [1, 2, 3, 2, 2] → 4. Original problem: neetcode.io/problems/fruit-into-baskets

Complexity

BestO(n)

AverageO(n)

WorstO(n)

SpaceO(1)

The map never holds more than 3 keys.

Key idea

This is "longest subarray with at most 2 distinct values".
Add fruits[r] to a count map.
While the map has 3 keys, decrement fruits[l] and remove it at 0.
Track the widest valid window.

Common mistakes

Forgetting to remove keys whose count drops to 0, so size() stays 3.
Restarting from scratch on a third type is O(n²).

Solution

Java

int totalFruit(int[] fruits) {
    Map<Integer, Integer> count = new HashMap<>();
    int l = 0, best = 0;
    for (int r = 0; r < fruits.length; r++) {
        count.merge(fruits[r], 1, Integer::sum);
        while (count.size() > 2) {
            count.merge(fruits[l], -1, Integer::sum);
            if (count.get(fruits[l]) == 0) count.remove(fruits[l]);
            l++;
        }
        best = Math.max(best, r - l + 1);
    }
    return best;
}

Python

def totalFruit(fruits: List[int]) -> int:
    count = defaultdict(int)
    l = best = 0
    for r, f in enumerate(fruits):
        count[f] += 1
        while len(count) > 2:
            count[fruits[l]] -= 1
            if count[fruits[l]] == 0: del count[fruits[l]]
            l += 1
        best = max(best, r - l + 1)
    return best

C++

int totalFruit(vector<int>& fruits) {
    unordered_map<int, int> count;
    int l = 0, best = 0;
    for (int r = 0; r < (int)fruits.size(); r++) {
        count[fruits[r]]++;
        while (count.size() > 2) {
            if (--count[fruits[l]] == 0) count.erase(fruits[l]);
            l++;
        }
        best = max(best, r - l + 1);
    }
    return best;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
One type One basket is enough.	`fruits = [4, 4, 4]`	`3`
Alternating three types The best stretch is [1, 3, 1, 3].	`fruits = [1, 2, 1, 3, 1, 3]`	`4`
Single tree Pick the one fruit.	`fruits = [7]`	`1`
Two types The window never needs to shrink.	`fruits = [0, 1, 0, 1]`	`4`