← DSA Atlas
Dedicated problem page · #904

Fruit Into Baskets

MediumSliding WindowLongest window with at most K distinctTwo pointers with a count map
Solve on LeetCode ↗
904
MediumSliding WindowTwo pointers with a count mapLongest window with at most K distinct

Fruit Into Baskets

You start at some tree in a row of fruit trees given by the array fruits, where fruits[i] is the fruit type on tree i. You carry two baskets, each holding a single (unlimited) fruit type, and you pick one fruit from every tree moving right until you cannot. Return the maximum number of fruits you can pick — equivalently, the length of the longest contiguous subarray containing at most two distinct values.

Open official problem prompt ↗
In plain English

Find the longest contiguous stretch of trees whose fruits come from at most two types.

Picture it like this

Walking down an orchard row with exactly two baskets, you keep collecting until a third fruit type appears; then you must have started later, so you drop the oldest trees from your route until only two types remain, always remembering the longest successful walk.

Example
Input
fruits = [1, 2, 3, 2, 2]
Output
4
Why
The subarray [2, 3, 2, 2] uses only two fruit types (2 and 3) and has length 4, the longest such run.
Constraints
1 <= fruits.length <= 10^50 <= fruits[i] < fruits.length
Pattern lesson

See the pattern, then code

Longest window with at most K distinct
Recognition clue

The phrase 'longest contiguous run with at most 2 distinct types' is the canonical at-most-K-distinct sliding window (here K = 2). A limit on the number of distinct elements inside a window is the trigger.

↗
Sliding Window

Longest, shortest, maximum, or minimum contiguous subarray or substring.. Expand a window to the right, tracking a count of each fruit type inside it. Whenever the window holds more than two distinct types, shrink from the left until only two remain. The best window width seen is the answer.

New words, made simpleKnow these before the algorithm
Distinct count
The number of different values currently inside the window.
At-most-K window
A sliding window constrained to contain no more than K distinct values (K = 2 here).
Window width
right - left + 1, the number of elements currently in the window.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Check every subarray

Quadratic in the worst case; too slow at n = 10^5.

For each start, extend the end while distinct types stay <= 2.

Time O(n^2)Space O(1)
Track last positions of two types

Correct but fiddly bookkeeping and easy to get wrong.

Manually remember the two current types and their last-seen indices.

Time O(n)Space O(1)
Best choiceSliding window with count map

Clean, general (works for any K), and linear.

Grow the window and shrink whenever distinct types exceed 2.

Time O(n)Space O(1)
The rule we keep true

Invariant

After each iteration the window [left, right] is the longest window ending at right that contains at most two distinct fruit types.

Why this is correct

Reasoning

The count map's size is exactly the number of distinct types in the window. Whenever it exceeds two we shrink from the left, which can only reduce distinct types, until the constraint holds again. left only moves forward, so every index is added and removed at most once, giving linear time; taking the max width over all right ends yields the global optimum.

The algorithm in three movesSay these aloud before coding
1Keep a count map of fruit types in the current window

right=2 fruit 3 -> counts {1:1,2:1,3:1} (3 distinct) -> shrink drop 1, left=1

2Add the entering fruit on the right

window [2,3] -> counts {2:1,3:1}

3While the map holds more than two distinct types, decrement the left fruit and drop it at zero, advancing left

expand to [2,3,2,2] -> best=4

4Update the best length with the current window width

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
21
32
23
24
1 · Readf=1
2 · Ask> 2 distinct?
3 · Update statecount={1:1}, left=0
4 · Resultbest=1.
Key takeaway

The longest window [2,3,2,2] holds only two fruit types and has length 4.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 6-8State setup

    A count map of types in the window, plus left pointer and best length.

  2. 2
    Lines 9-10Grow right

    Add the entering fruit to the window counts.

  3. 3
    Lines 11-15Shrink on violation

    While more than two distinct types are present, remove the leftmost fruit and delete it at zero, advancing left.

  4. 4
    Lines 16Track the best

    Record the widest valid window seen so far.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • A single type throughout returns the whole length
  • All distinct types returns 2 (any two adjacent trees)
  • Array of length 1 returns 1
  • The optimal window sitting at the very end of the array
!

Common beginner mistakes

  • Using an if instead of a while when shrinking, which fails to remove enough elements to restore the constraint
  • Forgetting to delete a type when its count hits zero, so len(count) overcounts distinct types
  • Confusing 'at most 2 distinct' with 'exactly 2 distinct' (single-type arrays must still count fully)
  • Resetting left too far and skipping valid windows
Check your understanding

How would you generalize this solution to allow at most K baskets instead of exactly two?

More in Sliding Window

#3Longest Substring Without Repeating CharactersVariable-size sliding window with last-seen index#424Longest Repeating Character ReplacementVariable-size window constrained by replaceable slots#76Minimum Window SubstringShrinkable window covering a multiset requirement#30Substring with Concatenation of All WordsWord-aligned sliding window over fixed-length tokens#121Best Time to Buy and Sell StockRunning minimum with best forward difference#209Minimum Size Subarray SumShrinking window on a sum threshold