904. Fruit Into Baskets

Problem¶

Find the length of the longest contiguous subarray containing at most 2 distinct values.

Example:

fruits = [1,2,3,2,2] -> 4
best window: [2,3,2,2]

Key trick¶

Use a sliding window.

Expand the right end.
Count fruit types in the current window.
While there are more than 2 types, move the left end rightward.
Track the maximum window length.

Trap¶

Treating it like a subsequence instead of a contiguous subarray.
Restarting from many positions, which becomes \(O(n^2)\).
Forgetting to remove a fruit type from the counter when its count becomes 0.
Missing that "start anywhere, move only right" means "choose any contiguous segment".

Why is it interesting?¶

It is a clean "at most K distinct" sliding-window pattern.

Very common interview template.
Simple to code.
Tests correctness and window-shrinking intuition.

Python solution¶

class Solution:
    def totalFruit(self, fruits: list[int]) -> int:
        # Sliding window with counts of fruit types inside the window.
        counts = {}
        l = 0
        best = 0

        for r, fruit in enumerate(fruits):
            counts[fruit] = counts.get(fruit, 0) + 1

            # Keep only at most 2 distinct fruit types.
            while len(counts) > 2:
                left_fruit = fruits[l]
                counts[left_fruit] -= 1
                if counts[left_fruit] == 0:
                    del counts[left_fruit]
                l += 1

            # Window [l, r] is valid.
            best = max(best, r - l + 1)

        return best

Comment on my solution¶

Your solution is correct on many cases, but it is not a good interview answer.

It explores multiple starting points with a stack, so worst-case time is \(O(n^2)\).
The intended solution is \(O(n)\) with one sliding window.
Using -1 as a sentinel for t2 is brittle even if constraints make it safe.
The stack.append((i, t2)) branching is clever, but harder to reason about than the standard window pattern.

A counterexample for performance:

fruits = [1,2,3,4,5,6,...]

Your code keeps retrying from many indices.
Sliding window processes each index at most twice.

## Solution
# WRONG
class Solution:
    def totalFruit(self, fruits: list[int]) -> int:
        stack = [(0, fruits[0])]
        best_count = 0
        while stack:
            i, t1 = stack.pop()
            count = 0
            t2 = -1
            while i < len(fruits):
                if fruits[i] == t1:
                    count += 1
                elif fruits[i] == t2:
                    count += 1
                elif t2 == -1:
                    t2 = fruits[i]
                    stack.append((i, t2))
                    count += 1
                else:
                    break
                i += 1
            best_count = max(best_count, count)
        return best_count

# WRONG
# written after reading AI comments
class Solution:
    def totalFruit(self, fruits: list[int]) -> int:
        max_window_length = 0
        left, right = 0, 0
        while right < len(fruits):
            right += 1
            seen = set()
            for i in range(left, right):
                seen.add(fruits[i])
            if len(seen) <= 2:
                max_window_length = max(max_window_length, right - left)
                continue
            while len(seen) > 2:
                left += left
                seen = set()
                for i in range(left, right):
                    seen.add(fruits[i])
        return max_window_length

# WORKS
# written way after, while practicing with Anki (2026-07-27)
class Solution:
    def totalFruit(self, fruits: list[int]) -> int:
        # val -> index
        last_seen_in_window = {}
        left = 0
        best = 0

        for right, fruit in enumerate(fruits):
            if fruit not in last_seen_in_window:
                last_seen_in_window[fruit] = right
            if len(last_seen_in_window) == 3:
                left_fruit_rm_idx = min(last_seen_in_window.values())
                left_fruit_rm = fruits[left_fruit_rm_idx]
                del last_seen_in_window[left_fruit_rm]
                left = left_fruit_rm_idx + 1

            last_seen_in_window[fruit] = right

            best = max(best, right - left + 1)

        return best