Fruit Into Baskets

1. Define the problem

You may pick fruit from a contiguous stretch of trees while holding at most two types. Find the longest subarray with at most 2 distinct values . Grow right while tracking type counts; shrink left whenever a third type appears.

Constraints

1 ≤ fruits.length ≤ 10⁵
0 ≤ fruits_i < fruits.length

Example

Inputfruits = [1, 2, 1]

Output3

Explanation Pick all three trees with baskets for types 1 and 2.

2. Visualize the solution

At most two fruit types in the window

Statusvalid

Types {1,2}; best = 2.

What happens in this step

window = [0, 1]  fruits [1, 2]

before: counts = {1:1}
  add fruits[1] = 2 → counts = {1:1, 2:1}

Two distinct types so far — window valid; best becomes 2.

Step 1 of 4

Steps to visualize

Grow right and increment the count for that fruit type in a map.
When a third distinct type appears, shrink left until only two remain.
Delete a type from the map when its count hits zero.
After each valid step, update best with the current window length.
Continue until right reaches the end of the array.

3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

At most two fruit types in the window

Statusvalid

Types {1,2}; best = 2.

What happens in this step

window = [0, 1]  fruits [1, 2]

before: counts = {1:1}
  add fruits[1] = 2 → counts = {1:1, 2:1}

Two distinct types so far — window valid; best becomes 2.

Step 1 of 4

4. Solution

Solution

solution.tsTypeScript

function totalFruit(fruits) {
  const counts = new Map();
  let left = 0;
  let best = 0;

  for (let right = 0; right < fruits.length; right++) {
    const type = fruits[right];
    counts.set(type, (counts.get(type) ?? 0) + 1);

    while (counts.size > 2) {
      const leftType = fruits[left];
      const newCount = counts.get(leftType) - 1;
      if (newCount === 0) {
        counts.delete(leftType);
      } else {
        counts.set(leftType, newCount);
      }
      left++;
    }

    best = Math.max(best, right - left + 1);
  }

  return best;
}

Time: O(n)
Space: O(1)

5. Test cases

Test cases

Input	Expected	Covers
`fruits = [1, 2, 1]`	`3`	Docstring example
`fruits = [5]`	`1`	Single tree
`fruits = [0, 1, 0, 1, 0, 1]`	`6`	Entire array with only two types
`fruits = [3, 3, 3, 3]`	`4`	All identical elements
`fruits = [1, 2, 3, 2, 2]`	`4`	Classic three-type walkthrough
`fruits = [1, 0, 1, 4, 1, 4, 1, 2, 3]`	`5`	Best window of types 1 and 4 length 5
`fruits = [1, 2, 3, 4, 5]`	`2`	No repeats — every window caps at 2

Fruit Into Baskets