LeetCode · #904

Fruit Into Baskets Solution

Given an integer array fruits, return the maximum number of fruits you can pick with at most two types of fruit.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #904

🏗️

Pattern

Sliding Window — at most k distinct

You are visiting a row of fruit trees. Each tree has a type of fruit given by fruits[i]. You have two baskets, and each basket can only hold one type of fruit. Starting from any tree, you must pick exactly one fruit from every tree moving right — you stop when you encounter a third fruit type. Return the maximum number of fruits you can collect.

Example 1

 Input: fruits = [1, 2, 1]
Output: 3 // Pick all three — only 2 types (1 and 2) 

Example 2

 Input: fruits = [0, 1, 2, 2]
Output: 3 // Pick [1, 2, 2] — 2 types. Can't include 0 too (3 types). 

Example 3

 Input: fruits = [1, 2, 3, 2, 2]
Output: 4 // Pick [2, 3, 2, 2] — 2 types (2 and 3) 

Constraints

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

Section Two · Approach 1

Brute Force — O(n²)

For each starting index, extend rightward counting distinct types. Stop when you see a third type. Track the maximum window length.

Problem: O(n²) windows. A sliding window with a HashMap tracking fruit counts maintains at most 2 distinct types, shrinking from the left when a third appears — O(n).

Java — Brute Force

 class Solution {
public int totalFruit(int[] fruits) {
int max = 0;
for (int i = 0; i < fruits.length; i++) {
Set<Integer> types = new HashSet<>();
int j = i;
while (j < fruits.length) {
                types.add(fruits[j]);
if (types.size() > 2) break;
                j++;
            }
            max = Math.max(max, j - i);
        }
return max;
    }
}

Python — Brute Force

 class Solution:
def totalFruit(self, fruits: list[int]) -> int:
        max_len = 0 for i in range(len(fruits)):
            types = set()
            j = i
while j < len(fruits):
                types.add(fruits[j])
if len(types) > 2: break
j += 1
max_len = max(max_len, j - i)
return max_len

Metric	Value
Time	O(n²)
Space	O(1) — set has at most 3 elements

Section Three · Approach 2

Sliding Window — O(n)

Maintain a window [left, right] with a HashMap counting each fruit type's occurrences. When the map has more than 2 keys (3+ types), shrink from the left — decrementing counts and removing keys that reach 0.

💡 Mental model: You're walking down a fruit orchard with two baskets. You pick fruits as you go. If you encounter a third kind, you must "forget" the earliest fruits until you're back to 2 types. Your HashMap is an inventory of what's in each basket — when a third type appears, you drop the oldest fruits until one basket empties.

Algorithm

Step 1: left = 0, HashMap basket, maxLen = 0.
Step 2: For each right: add fruits[right] to basket (increment count).
Step 3: While basket.size() > 2: decrement basket[fruits[left]]. If count reaches 0, remove the key. left++.
Step 4: Update maxLen = max(maxLen, right - left + 1).

🎯 Generalization:

This is the "longest subarray with at most K distinct elements" pattern. Here K=2.
The same template works for any K — just change the basket.size() > 2 condition to > K.
This pattern appears in LC 904, LC 340 (Longest Substring with At Most K Distinct Characters), and LC 159 (Longest Substring with At Most Two Distinct Characters).

Section Four · Trace

Visual Walkthrough

Trace through fruits = [1, 2, 3, 2, 2]:

Sliding Window — at most 2 distinct fruit types

Section Five · Implementation

Code — Java & Python

Java — Sliding Window + HashMap

 import java.util.HashMap;
class Solution {
public int totalFruit(int[] fruits) {
HashMap<Integer, Integer> basket = new HashMap<>();
int left = 0, maxLen = 0;
for (int right = 0; right < fruits.length; right++) {
            basket.merge(fruits[right], 1, Integer::sum);
while (basket.size() > 2) {
int leftFruit = fruits[left];
                basket.put(leftFruit, basket.get(leftFruit) - 1);
if (basket.get(leftFruit) == 0) basket.remove(leftFruit);
                left++;
            }

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

Python — Sliding Window + dict

 from collections import defaultdict class Solution:
def totalFruit(self, fruits: list[int]) -> int:
        basket = defaultdict(int)
        left = max_len = 0 for right in range(len(fruits)):
            basket[fruits[right]] += 1 while len(basket) > 2:
                basket[fruits[left]] -= 1 if basket[fruits[left]] == 0:
del basket[fruits[left]]
                left += 1
max_len = max(max_len, right - left + 1)
return max_len

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Brute Force	O(n²)	O(1)	Check all subarrays
Sliding Window ← optimal	O(n)	O(1)	HashMap has at most 3 keys; each element enters/leaves once

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
All same	`[3, 3, 3]`	One type — entire array fits. Answer = n.
Two types	`[1, 2, 1, 2]`	Exactly 2 types — all fit. Answer = n.
Single element	`[5]`	Trivial → 1.
All distinct	`[1, 2, 3, 4]`	Best is any adjacent pair → 2.
Third type at end	`[1, 1, 2, 3]`	Window [1,1,2] = 3, then shrink when 3 enters.

⚠ Common Mistake: Forgetting to remove map keys when their count drops to 0. If you only decrement without removing, map.size() stays inflated, causing the window to shrink more than necessary. Always delete keys with 0 count.

← Back to Sliding Window problems

LearningTree

LC 904 · Fruit Into Baskets — Solution & Explanation | DSA Guide