visual walkthrough
Fruit Into Baskets
Longest window with at most two distinct values, in disguise.
The idea
It's the longest subarray with at most two distinct values. A map of counts inside the window tells you how many types you hold.
When a third type enters, drop trees from the left until one type's count falls to zero.
Complexity
| approach | time | space |
|---|---|---|
| Try every start | O(n²) | O(1) |
| Sliding window | O(n) | O(1) |