Skip to main content
Ace Hired
All coding problems

Fruit Into Baskets

Mediumsliding windowSliding windowsliding-windowarrayshash-map

Maintained by Vikas D, software engineer

You walk along a single row of trees. Each tree gives one type of fruit, encoded as an integer in the array. You carry two baskets, and each basket can hold only one fruit type, so across your whole walk you may collect at most two different types.

You may begin at any tree, but once you start you must take one fruit from every tree as you move right, never skipping. The moment you reach a tree whose type matches neither basket, you have to stop.

Because you can pick your starting tree freely, the question becomes: which contiguous stretch of trees contains the most fruits while spanning no more than two distinct types? The answer is the length of that stretch.

Return that maximum count of fruits.

Examples

Input: fruits = [1, 2, 1]
Output: 3

The whole row uses only types 1 and 2, which fit in the two baskets, so all three trees can be picked.

Input: fruits = [0, 1, 2, 2]
Output: 3

Starting at index 1 gives [1, 2, 2], using types 1 and 2. Including the leading 0 would force a third type, so 3 is the best.

Input: fruits = [1, 2, 3, 2, 2]
Output: 4

The stretch [2, 3, 2, 2] from index 1 to 4 holds only types 2 and 3 across four trees, which beats any window that includes the opening 1.

Constraints

  • 1 <= fruits.length <= 10^5
  • 0 <= fruits[i] < fruits.length
  • Every fruit value is a non-negative integer; there is no upper bound on how many distinct types appear overall.
  • The picked trees must be contiguous (you cannot skip a tree once you start).

Visible test cases

  • totalFruit([1,2,1]) == 3
  • totalFruit([0,1,2,2]) == 3
  • totalFruit([1,2,3,2,2]) == 4
  • totalFruit([3,3,3,1,2,1,1,2,3,3,4]) == 5
  • totalFruit([1]) == 1
  • totalFruit([1,1,1,1]) == 4
  • totalFruit([0,1,2,3,4]) == 2

Hints

Hint 1

Reframe the story: you are looking for the longest contiguous subarray that contains at most two distinct values. The baskets are just a cap of two on the number of types in your window.

Hint 2

A window that grows from the right and shrinks from the left fits this perfectly. Track how many of each type currently sit inside the window with a hash map keyed by fruit type.

Hint 3

Whenever adding a new tree pushes the number of distinct types above two, advance the left edge and decrement counts until exactly two types remain, then record the window length.

Loading the editor...

Approaches

Brute force over all start points

Time O(n^2) · Space O(1)

Try every possible starting tree, then extend rightward while the running set of distinct types stays at two or fewer, and keep the longest such extension.

  1. For each index i, treat it as the start of a pick.
  2. Walk forward from i with a small set of seen types, adding each new type.
  3. Stop the inner walk as soon as a third distinct type would be added.
  4. Track the largest count of trees covered across all starting points.

Optimal sliding window with a count map

Time O(n) · Space O(1)

Maintain one window that always holds at most two distinct types. Expand the right edge through every tree, and when a third type appears, shrink the left edge until the window is valid again. The best window length seen is the answer.

  1. Keep a hash map from fruit type to how many of that type are inside the window, plus a left pointer.
  2. Move the right pointer over each tree, incrementing that type's count in the map.
  3. While the map holds more than two keys, decrement the count at the left pointer's type and remove the key when it hits zero, then advance left.
  4. After each step the window is valid, so update the best length with right minus left plus one.
  5. Return the best length once the right pointer reaches the end.

Common mistakes

  • Treating the limit as two fruits rather than two fruit types. The baskets cap distinct types, not total quantity, so a window of many identical fruits is fine.
  • Forgetting to delete a type from the map when its count drops to zero, which leaves a stale key and makes the window look like it still has too many types.
  • Returning the count of distinct types or the number of windows instead of the window length itself.
  • Assuming you must start at index 0. The best stretch often sits in the middle of the row.
  • Shrinking the window with an if instead of a while, which can leave three types inside after a single step.

Follow-up variations

  • Generalize to at most k baskets (at most k distinct types) and return the longest valid window.
  • Return the actual start and end indices of the best stretch, not just its length.
  • Handle a streaming version where fruits arrive one at a time and you must report the current best window so far.
  • Allow the baskets to be emptied once at a chosen point, letting one window pause and resume, and find the new maximum.

Recommended problems

Build the rest of your prep