Problem Statement

904. Fruit Into Baskets asks us to find the maximum number of consecutive fruits we can collect from a row of fruit trees, given that we can only use two baskets and each basket can hold only one type of fruit.

The key constraints are:

• Start from any position and move only to the right
• Must pick exactly one fruit from every tree we visit
• Stop when we encounter a third fruit type
• Find the longest possible sequence

This is essentially asking: "What's the longest contiguous subarray containing at most 2 distinct elements?"

Algorithm Walkthrough

Key Idea

Use a sliding window with hashmap to track fruit types and their counts in the current window.

The approach:

1. Expand the right pointer to include new fruits
2. When we have more than 2 fruit types, shrink from the left until we're back to 2 types
3. Track the maximum window size throughout

Algorithm Steps

def totalFruit(self, fruits: List[int]) -> int:
    counter = {}  # Track fruit types and counts
    left = 0
    max_fruits = 0

    for right, fruit in enumerate(fruits):
        # Add current fruit to window
        counter[fruit] = counter.get(fruit, 0) + 1

        # Shrink window if more than 2 fruit types
        while len(counter) > 2:
            counter[fruits[left]] -= 1
            if counter[fruits[left]] == 0:
                del counter[fruits[left]]
            left += 1

        # Update maximum
        max_fruits = max(max_fruits, right - left + 1)

    return max_fruits

Some Tricks

1. Avoid importing packages, try to use default data structures

Python dict is faster than defaultdict for simple cases like this. Using counter.get(fruit, 0) is more efficient than importing collections.defaultdict.

2. No need to compute the maximum value in each iteration

As in the specific case of LeetCode 904, when you're shrinking the window correctly using while len(counter) > 2, you only shrink just enough to make the window valid, then continue expanding right. So the longest valid window will usually survive to the end — but this is not guaranteed for every input.

However, your current solution has a bug: it returns rp - lp + 1 (the final window size) instead of the maximum window size encountered. This only works when the longest valid window happens to be at the end.

Corrected Solution

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        counter = {}
        left = 0
        max_fruits = 0

        for right, fruit in enumerate(fruits):
            # Add current fruit
            counter[fruit] = counter.get(fruit, 0) + 1

            # Shrink window if more than 2 types
            while len(counter) > 2:
                counter[fruits[left]] -= 1
                if counter[fruits[left]] == 0:
                    del counter[fruits[left]]
                left += 1

            # Update maximum window size
            max_fruits = max(max_fruits, right - left + 1)

        return max_fruits

Example Walkthrough

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

right=0: fruit=1, counter={1:1}, window=[1], max=1
right=1: fruit=2, counter={1:1,2:1}, window=[1,2], max=2  
right=2: fruit=1, counter={1:2,2:1}, window=[1,2,1], max=3
right=3: fruit=2, counter={1:2,2:2}, window=[1,2,1,2], max=4
right=4: fruit=3, counter={1:2,2:2,3:1}, len>2!
  - Shrink: left=0→4, counter={3:1,2:2}, window=[3,2,2], max=4
right=5: fruit=2, counter={3:1,2:3}, window=[3,2,2,2], max=4
right=6: fruit=2, counter={3:1,2:4}, window=[3,2,2,2,2], max=5

Result: 5

Complexity Analysis

Time Complexity: O(n)

• The outer loop runs exactly n times where n is the length of the fruits array
• Each element is visited at most twice: once by the right pointer when expanding, and once by the left pointer when shrinking
• Hash map operations (get, set, delete) are O(1) on average
• The while loop for shrinking might seem like it adds extra complexity, but it's amortized O(1):
  • Each element can only be removed from the window once
  • Total number of left pointer movements across all iterations ≤ n
  • So the total work done by the while loop is O(n) across the entire algorithm

Space Complexity: O(1)

• The hash map stores at most 3 fruit types at any time (briefly when we encounter a third type before shrinking)
• Since we're constrained to at most 2 types in a valid window, the space usage is constant
• We only use a few additional variables (left, max_fruits, etc.)
• Note: This is O(1) because the problem constraint limits us to 2 baskets, not because of the input size

Why This Is Optimal

• Time: We must examine each fruit at least once, so O(n) is optimal
• Space: We need to track fruit types in the current window, and since we're limited to 2 types, O(1) space is optimal for this approach

The sliding window technique efficiently finds the longest contiguous subarray with at most 2 distinct elements in optimal time and space complexity.