Pattern visualizer
Fruit Into Baskets
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. 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)..
At-most-2-distinct sliding window
time O(n)space O(1)step 1 / 8
1
[0]2
[1]3
[2]2
[3]2
[4]line 4
Add fruits[0]=1. Basket holds {1}. 1 distinct type — within the limit of 2.
Pseudocode
1FUNCTION totalFruit(fruits):2 count = a table of fruit type -> how many are in the window; l = 0; maxLen = 03 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 right7 maxLen = the larger of maxLen and the window size (r - l + 1)8 RETURN maxLen
← / → step · space play · Home restart