DSA Tracker

Visualize

Fruit Into Baskets

At-most-2-distinct sliding window

time O(n)space O(1)

You have exactly 2 baskets, so at any time the current window may contain at most 2 distinct fruit types. Slide a window right, tracking counts of each type; the instant a 3rd distinct type would enter, shrink from the left until only 2 types remain. The longest window seen along the way is the answer — no need to restart from scratch each time.

Details

Animated on: fruits = [1,2,3,2,2] — find the longest run of trees you can pick from with only 2 baskets (2 distinct fruit types).

Problem:Fruit Into BasketsMedium

Pattern:Sliding Window

At-most-2-distinct sliding window

step 1 / 8

1
[0]
2
[1]
3
[2]
2
[3]
2
[4]

Add fruits[0]=1. Basket holds {1}. 1 distinct type — within the limit of 2.

  • l=0· arr[0] = 1
  • r=0· arr[0] = 1
Pseudocode
1FUNCTION totalFruit(fruits):
2  count = a table of fruit type -> how many are in the window; l = 0; maxLen = 0
3  FOR each right edge r from 0 to the end of fruits:
4    add one to the count of fruits[r]
5    WHILE the table holds more than 2 distinct types:
6      remove one fruits[l] from the count (drop the type if it hits 0); move l one step right
7    maxLen = the larger of maxLen and the window size (r - l + 1)
8  RETURN maxLen

← / → step · space play · Home restart

Every step in words

Show all 8 steps
  1. Add fruits[0]=1. Basket holds {1}. 1 distinct type — within the limit of 2.
  2. Add fruits[1]=2. Basket holds {1,2}. Still 2 distinct types — window [0,1], maxLen=2.
  3. Add fruits[2]=3. Basket holds {1,2,3} — 3 distinct types! Too many for 2 baskets.
  4. Shrink from the left: remove fruits[0]=1 from the count. Basket is back to {2,3} — 2 types.
  5. Window [1,2] has length 2 — matches the current best, maxLen stays 2.
  6. Add fruits[3]=2. Basket holds {2,3} still — 2 types stays valid. Window [1,3], maxLen=3.
  7. Add fruits[4]=2. Basket still holds only {2,3} — valid! Window [1,4], length 4 beats the best: maxLen=4.
  8. Array exhausted. Longest run with at most 2 distinct types is [2,3,2,2] at indices 1-4. Answer: 4.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Fruit Into Baskets in the editorAll Sliding Window problemsBack to roadmap