Fruit Into Baskets
Trees are planted in a row and each produces one fruit type, given as an integer array. Starting at any tree and moving right, you pick one fruit per tree, but you carry only two baskets and each basket holds a single type. Return the maximum number of fruits you can collect.
- 1 ≤ n ≤ 10^5
- 0 ≤ fruits[i] < n
- Contiguous stretch of trees
- At most two distinct values in the window
- Longest window under a distinct-count limit
A question about contiguous ranges whose validity is monotonic (extending a valid window can only break it; shrinking an invalid window can only fix it) can be answered with two indices that both only move right. Each element enters and leaves the window once, giving O(n) instead of O(n^2) enumeration of subarrays.
This is "longest subarray with at most two distinct values". Maintain a map from fruit type to count within a window. Expand to the right; when the map has three keys, advance the left end, decrementing counts and removing keys that reach zero, until only two remain. Track the largest window length.
- Tracking only the last two types and the run length of the most recent one gives an O(1)-space variant without a map.