Fruit Into Baskets

LeetCode 904: Fruit Into Baskets Solution & Explanation

Problem Overview

TL;DR: The optimal solution uses a variable-size sliding window to find the longest contiguous subarray containing at most two distinct numbers.

The Fruit Into Baskets problem asks us to find the maximum number of fruits we can collect from a row of trees. The constraints dictate that we must pick fruits contiguously and can only hold two distinct types of fruit across our baskets. In algorithmic terms, we are given an array of integers and need to determine the length of the longest contiguous subarray that contains no more than two unique integers.

This is a popular interview question that tests your ability to optimize array traversals, making the LeetCode 904 solution a critical study point for efficiency.

Brute Force Approach for Fruit Into Baskets

The naive approach involves checking every possible contiguous segment of the array to see if it satisfies the condition. We iterate through each tree, treating it as the starting point, and extend to the right until we encounter a third unique fruit type.

Pseudo-code:

max_fruits = 0
for start from 0 to length - 1:
    unique_types = empty set
    current_count = 0
    for end from start to length - 1:
        add fruits[end] to unique_types
        if size of unique_types > 2:
            break
        current_count++
    max_fruits = max(max_fruits, current_count)
return max_fruits

Time Complexity Analysis: The time complexity is $O(N^2)$, where $N$ is the number of trees. In the worst case (e.g., an array like [1, 2, 1, 2, ...]), for each starting position, we might traverse nearly the entire remaining array. Given that $N$ can be up to $10^5$, an $O(N^2)$ solution requires approximately $10^{10}$ operations, resulting in a Time Limit Exceeded (TLE) error.

Why it fails: The brute force method performs redundant work. When we move the start position from i to i+1, we discard all information gathered about the segment starting at i, re-scanning elements we have already processed.

Algorithm Strategy: Sliding Window Patterns

1. State Management: Use a Hash Map (or a frequency array) to track the count of each fruit type currently inside the window.
2. Pointers: Initialize left and right pointers to 0. Initialize max_len to 0.
3. Expand: Iterate right from 0 to the end of the array. Add fruits[right] to the map.
4. Constraint Check: While the size of the map is greater than 2 (meaning we have 3 distinct types):
   • Decrement the count of fruits[left] in the map.
   • If the count becomes 0, remove the key from the map.
   • Increment left to shrink the window.
5. Update Result: Calculate the current window size (right - left + 1) and update max_len.
6. Output: Return max_len.

Execution Flow

Let's trace fruits = [1, 2, 3, 2, 2].

1. Init: left=0, right=0, map={}, max=0.
2. right=0 (Val: 1): Add 1. map={1:1}. Valid. max=1.
3. right=1 (Val: 2): Add 2. map={1:1, 2:1}. Valid. max=2.
4. right=2 (Val: 3): Add 3. map={1:1, 2:1, 3:1}. Size is 3 (Invalid).
   • Shrink: Remove fruits[left] (which is 1). map becomes {1:0, 2:1, 3:1}.
   • Remove key 1. map={2:1, 3:1}. Size is 2. Valid.
   • left moves to 1.
   • Current window [1, 2] (indices). len = 2 - 1 + 1 = 2. max stays 2.
5. right=3 (Val: 2): Add 2. map={2:2, 3:1}. Valid. len = 3. max=3.
6. right=4 (Val: 2): Add 2. map={2:3, 3:1}. Valid. len = 4. max=4.
7. End of array. Return 4.

Proof of Correctness

The algorithm is correct because it implicitly checks all valid windows that could potentially be the longest. For any ending position right, the algorithm maintains the smallest possible left such that [left, right] is valid. Since the window only shrinks when the constraint is violated, the window size right - left + 1 is always the maximum valid length ending at right. By iterating right through the entire array, we are guaranteed to encounter the global maximum.

Pattern Reuse Notes

The Sliding Window - Variable Size pattern used in Fruit Into Baskets is identical to the logic required for several other high-frequency interview problems. Mastering this structure allows you to solve:

• LeetCode 3: Longest Substring Without Repeating Characters - Instead of allowing 2 distinct characters, you allow distinct characters equal to the current window size (no duplicates).
• LeetCode 76: Minimum Window Substring - Expands to find all characters, then shrinks to find the minimum length.
• LeetCode 209: Minimum Size Subarray Sum - Expands until sum $\ge$ target, then shrinks to minimize length.
• LeetCode 219: Contains Duplicate II - A fixed or bounded sliding window variation checking for duplicates within distance $k$.

In all these cases, the core loop structure (expand right, while invalid shrink left, update result) remains constant.

Reference Implementation

C++ Solution for LeetCode 904

1#include <vector>
2#include <unordered_map>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9    int totalFruit(vector<int>& fruits) {
10        unordered_map<int, int> basket;
11        int left = 0;
12        int max_fruits = 0;
13        
14        for (int right = 0; right < fruits.size(); ++right) {
15            // Add current fruit to the basket
16            basket[fruits[right]]++;
17            
18            // If we have more than 2 types of fruit, shrink the window
19            while (basket.size() > 2) {
20                basket[fruits[left]]--;
21                if (basket[fruits[left]] == 0) {
22                    basket.erase(fruits[left]);
23                }
24                left++;
25            }
26            
27            // Update the maximum number of fruits
28            max_fruits = max(max_fruits, right - left + 1);
29        }
30        
31        return max_fruits;
32    }
33};

Java Solution for LeetCode 904

1import java.util.HashMap;
2import java.util.Map;
3
4class Solution {
5    public int totalFruit(int[] fruits) {
6        Map<Integer, Integer> basket = new HashMap<>();
7        int left = 0;
8        int maxFruits = 0;
9        
10        for (int right = 0; right < fruits.length; right++) {
11            // Add current fruit to the basket
12            basket.put(fruits[right], basket.getOrDefault(fruits[right], 0) + 1);
13            
14            // If we have more than 2 types, shrink from the left
15            while (basket.size() > 2) {
16                basket.put(fruits[left], basket.get(fruits[left]) - 1);
17                if (basket.get(fruits[left]) == 0) {
18                    basket.remove(fruits[left]);
19                }
20                left++;
21            }
22            
23            // Update max length
24            maxFruits = Math.max(maxFruits, right - left + 1);
25        }
26        
27        return maxFruits;
28    }
29}

Python Solution for LeetCode 904

1from collections import defaultdict
2
3class Solution:
4    def totalFruit(self, fruits: list[int]) -> int:
5        basket = defaultdict(int)
6        left = 0
7        max_fruits = 0
8        
9        for right in range(len(fruits)):
10            # Add current fruit to the basket
11            basket[fruits[right]] += 1
12            
13            # If we have more than 2 types, shrink from the left
14            while len(basket) > 2:
15                basket[fruits[left]] -= 1
16                if basket[fruits[left]] == 0:
17                    del basket[fruits[left]]
18                left += 1
19            
20            # Update max length
21            max_fruits = max(max_fruits, right - left + 1)
22            
23        return max_fruits