904. Fruit Into Baskets

At a Glance

• Topic: sliding-window
• Pattern: Sliding Window
• Difficulty: Medium
• Companies: Google, Amazon, Meta, Apple, DoorDash
• Frequency: Medium
• LeetCode: 904

Problem (one-liner)

Given an integer array tree where tree[index] is fruit type at that tree, you have two baskets and each holds a single type. Pick a contiguous subarray (prefix of harvest) maximizing length while using at most two distinct fruit types.

Recognition Cues

• "At most K distinct" with K = 2
• Longest subarray with ≤2 unique values
• Map or array counts + distinct tracking

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute force — every subarray + set — O(n³) / O(n²) with hashing per window.
• Better — sliding window with frequency map — O(n) time / O(1) space (bounded types if range small).
• Optimal — expand right, shrink left while distinct > 2.

Optimal Solution

Go

func totalFruit(tree []int) int {
	count := make(map[int]int)
	left := 0
	best := 0
	for right := 0; right < len(tree); right++ {
		count[tree[right]]++
		for len(count) > 2 {
			count[tree[left]]--
			if count[tree[left]] == 0 {
				delete(count, tree[left])
			}
			left++
		}
		width := right - left + 1
		if width > best {
			best = width
		}
	}
	return best
}

JavaScript

function totalFruit(tree) {
	const countByType = new Map();
	let left = 0;
	let best = 0;
	for (let right = 0; right < tree.length; right++) {
		const type = tree[right];
		countByType.set(type, (countByType.get(type) ?? 0) + 1);
		while (countByType.size > 2) {
			const leftType = tree[left];
			countByType.set(leftType, countByType.get(leftType) - 1);
			if (countByType.get(leftType) === 0) {
				countByType.delete(leftType);
			}
			left++;
		}
		const width = right - left + 1;
		if (width > best) {
			best = width;
		}
	}
	return best;
}

Walkthrough

Input: tree = [1,2,1]

Window grows; when a third type would enter, shrink from left until at most two types remain.

Invariant: window always contains ≤2 distinct keys in count.

Edge Cases

• Fewer than 3 elements
• Only one fruit type entire row
• Types are arbitrary integers

Pitfalls

• Using set of positions instead of counts — removal logic breaks for duplicates
• Forgetting to delete key when count hits zero

Similar Problems

• 424. Longest Repeating Character Replacement — budgeted uniformity vs distinct cap.
• 3. Longest Substring Without Repeating — all distinct (stronger than K distinct).
• 1004. Max Consecutive Ones III — binary + flip budget.

Variants

• K baskets — "Longest substring with at most K distinct characters" (general template).
• Count subarrays with exactly K distinct — AtMost(K) − AtMost(K−1).

Mind-Map Tags

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