904. Fruit Into Baskets

Quick Identifier

• Topic: sliding-window
• Pattern: Sliding Window (Variable Window with At Most K Distinct)
• Hint: Translate the convoluted "fruit basket" metaphor into standard DSA terms: "Find the longest contiguous subarray containing at most 2 distinct integers."
• Difficulty: Medium
• Companies: Google, Amazon, Meta, Apple, DoorDash
• LeetCode: 904

Quick Sights

• Time Complexity: O(n). We visit each tree exactly once with the right pointer, and at most once with the left pointer. Hash map insertions and deletions are $O(1)$.
• Space Complexity: O(1). The hash map stores the frequencies of the fruit types currently in the window. Because we strictly limit the window to contain at most 3 distinct types before shrinking it back to 2, the map's size never exceeds 3.
• Core Mechanism: Maintain a sliding window and a frequency map of fruit types. Expand right. If adding a new fruit pushes the size of your frequency map to 3 (meaning 3 distinct fruit types are in the window), your window is invalid. Shrink left until the frequency of one fruit type drops to 0. Delete that fruit from the map to restore validity (map size back to 2).

Concept Explanation

As a senior engineer, the first step is to strip away the "story" of the problem. You are given an array of integers and asked to find the maximum length of a subarray that contains no more than two unique values. This is literally just a hard-coded $K=2$ instance of the generic "Longest Substring with At Most K Distinct Characters" template.

1. The Expansion (Picking Fruit): Start walking down the row of trees (right pointer). Throw every fruit you encounter into your baskets (frequency map). Keep track of how many of each type you have.
2. The Limit (3rd Type): The moment you encounter a fruit that forces your frequency map to have 3 keys, you've violated the physical constraint (you only have 2 baskets). The current sequence of trees is broken.
3. The Contraction (Emptying a Basket): To fix the violation, you must walk your left pointer forward, abandoning trees. For every tree you pass, remove one fruit of that type from your map.
4. The Reset: You continue abandoning trees from the left until one of the fruit types completely runs out (its count hits 0). The moment a count hits 0, you physically throw that basket away (delete from the map). Now you only have 2 types of fruit again, the window is valid, and you can resume picking new fruits.

Diagram

This flowchart outlines the window expansion and map maintenance.

Study Pattern (SDE3+)

• 0–3 min: Immediately translate the problem text. State clearly: "This asks for the longest subarray with at most 2 distinct elements." Note the $O(1)$ space complexity because the map is bounded to size 3.
• Implementation pass: Be extremely careful to completely delete the key from the map when its value reaches 0. If you leave {fruitType: 0} in the map, map.size or len(map) will still report 3, and your while loop will run infinitely or shrink the window to nothing.
• 5 min extension: Discuss how to generalize this to $K$ baskets. The code is identical, just replace > 2 with > K. If the interviewer asks to solve the "Subarrays with Exactly K Distinct" variant, explain the math trick: AtMost(K) - AtMost(K-1).

Approaches

• Brute force — Check every possible subarray, put elements in a Set, if Set.size <= 2, check length. Time: $O(n^3)$.
• Sliding Window (Optimized) — Maintain a frequency map. Expand right, shrink left when the map exceeds 2 keys. Time: $O(n)$. (Always pick this)

Optimal Solution

Go

func totalFruit(tree []int) int {
	counts := make(map[int]int)
	left := 0
	best := 0
	
	for right := 0; right < len(tree); right++ {
		fruit := tree[right]
		counts[fruit]++
		
		// If we have more than 2 types of fruit, the window is invalid.
		// We must shrink from the left until a fruit type is completely removed.
		for len(counts) > 2 {
			leftFruit := tree[left]
			counts[leftFruit]--
			
			// Critical step: completely remove the key so len(counts) drops
			if counts[leftFruit] == 0 {
				delete(counts, leftFruit)
			}
			left++
		}
		
		width := right - left + 1
		if width > best {
			best = width
		}
	}
	
	return best
}

JavaScript

function totalFruit(tree) {
	const counts = new Map();
	let left = 0;
	let best = 0;
	
	for (let right = 0; right < tree.length; right++) {
		const fruit = tree[right];
		counts.set(fruit, (counts.get(fruit) || 0) + 1);
		
		// Shrink window if we have more than 2 distinct fruit types
		while (counts.size > 2) {
			const leftFruit = tree[left];
			counts.set(leftFruit, counts.get(leftFruit) - 1);
			
			// Critical step: completely remove the key so counts.size drops
			if (counts.get(leftFruit) === 0) {
				counts.delete(leftFruit);
			}
			left++;
		}
		
		const width = right - left + 1;
		if (width > best) {
			best = width;
		}
	}
	
	return best;
}

Walkthrough

Input: tree = [3,3,3,1,2,1,1,2,3,3,4]

Output: 5

Edge Cases

• tree has length 1 or 2 (Returns tree.length immediately, as it's impossible to exceed 2 types).
• All trees are the exact same fruit type (Returns tree.length).

Pitfalls

• Storing the actual indices of the fruits instead of their counts. The window validity depends entirely on the frequency of the types, not their positions.
• Forgetting to delete the key from the map when the count reaches 0. If you just do map[fruit] = 0, the map still physically contains the key, and map.size will remain too high.

Similar Problems

• 424. Longest Repeating Character Replacement — budgeted uniformity vs distinct cap.
• 3. Longest Substring Without Repeating — all distinct (which is functionally At Most right - left + 1 Distinct).
• 992. Subarrays with K Different Integers — The Hard variant.

Mind-Map Tags

#sliding-window #at-most-k-distinct #two-types #frequency-map #longest-window