Fruit into Baskets

Find the longest contiguous subarray containing at most two distinct fruit types.

sliding-window two-pointers hash-map

You are visiting a farm that has a single row of fruit trees. Each tree is represented by an integer in the list `fruits`, where each integer is a type of fruit. You have two baskets, and each basket can only hold one type of fruit. You may start at any tree, but once you start, you must pick exactly one fruit from every tree as you move from left to right without skipping. The moment you encounter a third type of fruit, you must stop.

Write a function `totalFruit(fruits: List[int]) -> int` that returns the maximum number of fruits you can collect.

In other words, find the maximum length of a contiguous subarray that contains at most two distinct integers.

Constraints

1 <= len(fruits) <= 100000
0 <= fruits[i] <= 100000
Your solution should run in O(n) time and O(1) extra space (beyond the input).

Example

>>> totalFruit([1,2,1])
3
>>> totalFruit([0,1,2,2])
3
>>> totalFruit([1,2,3,2,2])
4

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of a sliding window where the window always contains at most two distinct fruit types.

Maintain a dictionary counting how many of each fruit type are in the current window.

When a third type is added, shrink the window from the left until only two types remain.

Track the maximum window length seen at each step.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.