What is the brute force approach and complexity for Fruit Into Baskets?

For each start, walk right until a third type appears with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Fruit Into Baskets?

Grow right; while there are 3 types, shrink left until one type is gone with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Fruit Into Baskets?

Look for key signals in the prompt: "walk right from a starting tree, picking from every tree" indicates The answer is a contiguous range [l … r] → think window.; "maximum number of fruits" indicates We want the longest valid range → variable window that grows on the right and shrinks on the left.; "two baskets, one type each" indicates At most 2 distinct values in the window → we need the counts of each value to know when a value fully leaves..

Fruit Into Baskets

Medium·LeetCode #904Basic Anchor

LeetCode

Jump:

30-Second Mental ModelVariable Sliding Window + Frequency Map

Complexity:O(N²)→O(N)

Key Insight

Keep one window [left … right] and a map count[type] of how many fruits of each type are inside. The number of keys in the map is the number of types. Grow the window on the right every step. If a third type appears, move left forward and drop fruits until one type's count reaches 0 and it is removed from the map. Then the window is valid again, and its length is a candidate answer.

Core Validity Invariant

The window is valid when it contains at most 2 distinct fruit types (count.size() ≤ 2). How many fruits of each type does not matter.

Problem

There is a row of fruit trees. fruits[i] is the type of fruit on tree i.

You have two baskets, and each basket can hold only one type of fruit (but as many fruits of that type as you like).

You pick a starting tree and walk right, picking exactly one fruit from every tree you pass. You must stop as soon as you reach a tree whose fruit fits in neither basket.

Return the most fruits you can pick.

In other words: find the longest contiguous subarray that contains at most 2 different values.

Input

An integer array fruits, where fruits[i] is the type of fruit on tree i.

Output

One integer: the length of the longest contiguous subarray with at most 2 distinct values.

Example 1

Input: fruits = [1, 2, 1]

Output: 3

Only 2 types (1 and 2), so you can pick from all three trees.

Example 2

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

Output: 3

Start at tree 1 and pick [1, 2, 2]. Starting at tree 0 would stop at the third type (2) after only 2 fruits.

Example 3

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

Output: 4

Pick [2, 3, 2, 2] starting from tree 1.

Constraints

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

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
Do the picked trees have to be next to each other, or can I skip trees?
2.
What does "two baskets, one type each" really limit — the number of fruits, or the number of different types?
3.
If a block of trees is fine, is every smaller block inside it also fine?
4.
When a third type shows up, which trees could I stop picking from to make it fine again?
5.
What do I need to remember about the current block to know how many types it has?

Brute force approach

Idea

Try every starting tree. From each start, walk right and keep a small set of the types picked so far. As soon as the set holds 3 types, stop — that is exactly what the story says. Keep the longest walk.

Thinking process

1
The story already describes an algorithm: pick a start, walk right, stop at the third type.
2
I don't know the best start, so I try all of them.
3
For each start I keep a set of types. The walk is fine while the set has at most 2.
4
Once a third type joins, walking further can't remove it, so I break and try the next start.

Code & Implementation

brute.cpp

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int n = fruits.size();
        int best = 0;

        // Try every starting tree.
        for (int start = 0; start < n; start++) {
            set<int> types;  // fruit types picked from this start
            for (int end = start; end < n; end++) {
                types.insert(fruits[end]);
                // A third type means we must stop. Walking further
                // right can never remove it again.
                if (types.size() > 2) break;
                best = max(best, end - start + 1);
            }
        }
        return best;
    }
};

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int totalFruit(int[] fruits) {
        int n = fruits.length;
        int best = 0;

        // Try every starting tree.
        for (int start = 0; start < n; start++) {
            Set<Integer> types = new HashSet<>();  // fruit types picked from this start
            for (int end = start; end < n; end++) {
                types.add(fruits[end]);
                // A third type means we must stop. Walking further
                // right can never remove it again.
                if (types.size() > 2) break;
                best = Math.max(best, end - start + 1);
            }
        }
        return best;
    }
}

class Solution:
    def totalFruit(self, fruits: list[int]) -> int:
        n = len(fruits)
        best = 0

        # Try every starting tree.
        for start in range(n):
            types = set()  # fruit types picked from this start
            for end in range(start, n):
                types.add(fruits[end])
                # A third type means we must stop.
                if len(types) > 2:
                    break
                best = max(best, end - start + 1)

        return best

export function totalFruit(fruits: number[]): number {
    const n = fruits.length;
    let best = 0;

    // Try every starting tree.
    for (let start = 0; start < n; start++) {
        const types = new Set<number>(); // fruit types picked from this start
        for (let end = start; end < n; end++) {
            types.add(fruits[end]);
            // A third type means we must stop.
            if (types.size > 2) break;
            best = Math.max(best, end - start + 1);
        }
    }
    return best;
}

Complexity

Time O(N²)Space O(1)

The set never holds more than 3 types, so it is O(1) space. But with n = 10^5 and an array like [1,2,1,2,…], each start walks to the end, so it is about 5·10^9 steps — too slow.

Optimized approach

Idea

Start from brute force

Brute force walks from start i until it meets a third type at some tree j. Then it goes back to start i + 1 and walks over trees i+1 … j−1 again, even though it just saw them.

Find the repeated work

The trees between the old start and the stopping point are walked again for every new start. We already know they hold at most 2 types — we just forgot it.

Define the state — what variables do I need?

left, right: Everything between left and right is our current window — the trees we are picking from right now.
count: count[type] = how many fruits of that type are in the window. A type is only stored while its count is above 0.
count.size(): The number of different types in the window (the number of baskets we are using).
best: The longest valid window seen so far.

Define validity

The window is valid when it contains at most 2 distinct fruit types (count.size() ≤ 2). How many fruits of each type does not matter.

Define the transitions — when does each pointer move, and why is it safe?

Every step: right moves forward

count[fruits[right]]++

We always try to pick one more fruit. Growing can only add a type, never remove one, so this is the only moment the window can break.

While count.size() > 2

count[fruits[left]]--; if it is 0, erase that type; left++

A window with 3 types can only be fixed by removing a type completely. Any window that starts further left and ends at right also has those 3 types, so those starts are useless now and dropping them loses nothing.

After the shrink loop

best = max(best, right − left + 1)

Now the window is valid, and it is the longest valid window that ends at right.

What does the current window add to the answer?

For each right, the window [left … right] is the longest block ending at right with at most 2 types. The answer is the longest of these over all right.

Code & Implementation

optimal.cpp

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        unordered_map<int, int> count;  // fruit type -> how many in the window
        int left = 0, best = 0;

        for (int right = 0; right < (int)fruits.size(); right++) {
            count[fruits[right]]++;  // pick the fruit at right

            // More than 2 types: drop fruits from the left
            // until one type disappears completely.
            while (count.size() > 2) {
                int f = fruits[left];
                count[f]--;
                if (count[f] == 0) count.erase(f);  // type is gone from the window
                left++;
            }

            // Window [left .. right] now has at most 2 types.
            best = max(best, right - left + 1);
        }
        return best;
    }
};

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int totalFruit(int[] fruits) {
        Map<Integer, Integer> count = new HashMap<>();  // fruit type -> how many in the window
        int left = 0, best = 0;

        for (int right = 0; right < fruits.length; right++) {
            int fRight = fruits[right];
            count.put(fRight, count.getOrDefault(fRight, 0) + 1);  // pick the fruit at right

            // More than 2 types: drop fruits from the left
            // until one type disappears completely.
            while (count.size() > 2) {
                int fLeft = fruits[left];
                int c = count.get(fLeft);
                if (c == 1) {
                    count.remove(fLeft);  // type is gone from the window
                } else {
                    count.put(fLeft, c - 1);
                }
                left++;
            }

            // Window [left .. right] now has at most 2 types.
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

from collections import defaultdict

class Solution:
    def totalFruit(self, fruits: list[int]) -> int:
        count: dict[int, int] = defaultdict(int)
        left = 0
        best = 0

        for right in range(len(fruits)):
            count[fruits[right]] += 1

            # More than 2 types: drop fruits from the left
            # until one type disappears completely.
            while len(count) > 2:
                f = fruits[left]
                count[f] -= 1
                if count[f] == 0:
                    del count[f]
                left += 1

            best = max(best, right - left + 1)

        return best

export function totalFruit(fruits: number[]): number {
    const count = new Map<number, number>(); // fruit type -> count
    let left = 0;
    let best = 0;

    for (let right = 0; right < fruits.length; right++) {
        const fRight = fruits[right];
        count.set(fRight, (count.get(fRight) || 0) + 1);

        // More than 2 types: drop fruits from the left
        // until one type disappears completely.
        while (count.size > 2) {
            const fLeft = fruits[left];
            const c = count.get(fLeft)!;
            if (c === 1) {
                count.delete(fLeft);
            } else {
                count.set(fLeft, c - 1);
            }
            left++;
        }

        best = Math.max(best, right - left + 1);
    }
    return best;
}

Complexity

Time O(N)Space O(1)

Each index enters the window once (right) and leaves at most once (left), so the total work is at most 2N steps. The map never holds more than 3 keys, so space is O(1).

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	For each start, walk right until a third type appears	O(N²)	O(1)
Optimal	Grow right; while there are 3 types, shrink left until one type is gone	O(N)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“walk right from a starting tree, picking from every tree”The answer is a contiguous range [l … r] → think window.
“maximum number of fruits”We want the longest valid range → variable window that grows on the right and shrinks on the left.
“two baskets, one type each”At most 2 distinct values in the window → we need the counts of each value to know when a value fully leaves.

Contiguous range+maximum length+at most 2 distinct values→Variable Sliding Window + Frequency Map

This is the anchor of the frequency-map family. The window rule depends on what is inside the window (how many distinct types), not on a sum. Learn the core moves here: add on the right, remove on the left, and delete a key when its count reaches 0 so that count.size() is the number of distinct types. The next questions keep the same loop and only change the rule: exactly k distinct (GFG K Uniques), length − maxFreq ≤ k (Character Replacement), every count ≤ k (LC 2958), or covering a target (Minimum Window).

Don't make this mistake

Pattern confusion: using the Character Replacement rule

✗ while ((right - left + 1) - maxFreq > 2) { ... }

✓ while (count.size() > 2) { ... }

Fruit Into Baskets is NOT windowSize − maxFrequency ≤ 2; the condition is distinct types ≤ 2. windowSize − maxFreq counts how many fruits are not the most common type — that is the rule for Longest Repeating Character Replacement. Here, [1,2,1,2,1,2] is perfectly valid (2 types) even though 6 − 3 = 3 > 2.

Forgetting to erase a type when its count hits 0

✗ count[fruits[left]]--; left++;

✓ count[fruits[left]]--; if (count[fruits[left]] == 0) count.erase(fruits[left]); left++;

count.size() counts keys, including keys with value 0. If you don't erase, a type that already left the window still counts as a basket, and the loop shrinks forever (or far too much).

Using `if` instead of `while` to shrink

✗ if (count.size() > 2) { /* remove one fruit */ }

✓ while (count.size() > 2) { /* remove one fruit */ }

Removing one fruit may not remove a whole type. In [3,3,3,1,2], when 2 arrives you must drop all three 3s before the window is valid again.

Shrinking to just the last fruit

Some people reset left = right when a third type appears. That throws away the fruits of the type just before right, which can still be picked. For [1,2,1,1,3,1,1] the answer is 5 ([1,1,3,1,1]), but resetting to [3] gives only 4. Shrink one step at a time until a type disappears.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Sliding Window translate into production architectures and low-level memory mechanics.

LLD Machine Coding

Sliding Window Rate Limiter

Implementing token bucket and sliding log request throttlers in real backend services.

Explore Track

C++ Internals

Stack vs Heap, Placement new & Layout

Cache line locality when traversing contiguous windows in memory.

Explore Track

Longest Substring with K Unique Characters