AlgoViz
HomeSliding Window

Fruit Into Baskets

Medium

At most two distinct values

Problem

With two baskets each holding one fruit type, collect the most fruit from a row (longest subarray with at most 2 distinct values).

In simple words

It's the longest window with at most two distinct values — slide and shrink when a third sneaks in.

The idea

Two baskets each holding one fruit type is exactly 'longest subarray with at most 2 distinct values', so it is the k-distinct window with k fixed at 2. Recognising the restatement is the whole problem.

The trick

  • It is the k-distinct sliding window with k = 2.
  • The window length is the fruit count, since every element is picked.
1
2
1
2
3
0
1
2
3
4
k2

Step 1 of 14. Brute force: from each start, extend while at most 2 distinct values appear. Values: 1, 2, 1, 2, 3. k 2.

1/14
Brute force
timeO(n²)spaceO(1)

Every window.

1for (let i = 0; i < n; i++) {2  const seen = new Set();3  for (let j = i; j < n; j++) {4    seen.add(fruits[j]);5    if (seen.size > 2) break;6    best = Math.max(best, j - i + 1);7  }8}

Input

array
[1, 2, 1, 2, 3]

Memory

k
2

Output

best
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
fruits = [1, 2, 1]
Output:
3
Explanation:
Two kinds fit; grab all three.

Example 2

Input:
fruits = [0, 1, 2, 2]
Output:
3
Explanation:
The window [1,2,2] uses just two types.

Example 3

Input:
fruits = [1, 2, 3, 2, 2]
Output:
4
Explanation:
[2,3,2,2] is the longest two-type run.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.