The two baskets are really a constraint on any contiguous run of trees: a run is collectible exactly when it contains at most two distinct fruit types, and its length is the amount of fruit you get. So the problem reduces to “find the longest contiguous subarray that uses at most two distinct values” — a run-length maximization problem, which is precisely the shape a sliding window is built for. The right edge grows the run, the left edge repairs it, and every legal window between the two edges is a candidate for the answer.
The second realization is what to remember about the window. A set of types is not enough: when a run has to shrink, you need to know when a type has fully disappeared from the window, and that requires counts per type, not membership. The counter map {type: count} is the engine of the whole solution: picking a fruit increments its type, shrinking decrements the type that leaves, and a type is deleted from the map the moment its count reaches zero.
Brute Force: Every Start
Time O(n²)Space O(1)The rules literally describe an experiment: choose a starting tree, walk right, and count how far you get before a third type appears. Exhausting every possible start therefore must find the optimum. For each start i, extend a second pointer j while the stretch from i to j holds at most two distinct types; the moment a third type appears the stretch is dead, so record the best length seen so far and move on to the next start.
class Solution: def totalFruit(self, fruits: list[int]) -> int: best = 0 for i in range(len(fruits)): seen = set() for j in range(i, len(fruits)): seen.add(fruits[j]) if len(seen) > 2: # a third type: baskets overflow break best = max(best, j - i + 1) return bestWhy it is quadratic: the early break saves nothing in the worst case. If the row holds only one or two distinct types, the break never fires and every start scans to the end: n + (n-1) + ... + 1 ≈ n²/2 checks before the answer surfaces — unacceptable when fruits.length can reach 10^5. Space stays flat (the set never holds more than 3 types before breaking), but the deeper problem is information throwaway: every start forgets what the previous start computed, even though consecutive starts share almost all the same trees.
Correctness: every possible start and extendable length is enumerated, so the longest legal run is measured at least once.
Sliding Window with Type Counter
OptimalTime O(n)Space O(1)Keep one window instead of restarting. left and right delimit the current run; each step the right edge picks one fruit and adds its type to the counter. There are only two outcomes. If the counter still holds at most two types, the window is legal — measure it against best and grow. If it holds three, the window is illegal — slide the left edge forward, decrementing the types that leave, until some type count hits zero and that type is deleted from the counter. Deleting a type always restores the two-basket limit, so the while loop stops, and best is only ever read on a legal window.
class Solution: def totalFruit(self, fruits: list[int]) -> int: count = {} # fruit type -> how many trees of that type are in the window left = 0 best = 0 for right, kind in enumerate(fruits): count[kind] = count.get(kind, 0) + 1 while len(count) > 2: # a third type joined: shrink from the left left_kind = fruits[left] count[left_kind] -= 1 if count[left_kind] == 0: del count[left_kind] # type fully gone: free one basket left += 1 best = max(best, right - left + 1) return bestThe mechanism deserves a slow-motion look — run the file example [1, 2, 3, 2, 2] and watch the counter: the shrink fires exactly when a third type appears, and it stops on the spot where a type count hits zero and that type leaves the counter.
Trees
no fruit picked yet — the window is empty
Basket counter (type: count)
a type leaves the counter only when its count hits zero — that is what frees a basket and ends the shrink
Goal: the longest CONTIGUOUS run of trees that contains at most two distinct fruit types. A contiguous run can only grow at its edges, so two pointers fit: left marks the first tree of the window, right the tree being picked right now. The two baskets are a rule about the run, not two fixed slots — any run holding at most two types fits, and the counter tracks how many trees of each type are inside.
Same walk on [0, 1, 2, 2] — watch the shrink evict type 0 while the surviving type 2 gets re-picked and stacks count 2 into its basket, so the best window stays at 3 trees.
Trees
no fruit picked yet — the window is empty
Basket counter (type: count)
a type leaves the counter only when its count hits zero — that is what frees a basket and ends the shrink
Example [0, 1, 2, 2]. Same window walk — this time the shrink fires before the row ends, so watch the counter drop an entry while a re-picked type stacks up in its basket.
On [1, 2, 1] no shrink ever fires — watch the count for type 1 climb to 2, because re-picking a type that already owns a basket never offends the two-basket rule.
Trees
no fruit picked yet — the window is empty
Basket counter (type: count)
a type leaves the counter only when its count hits zero — that is what frees a basket and ends the shrink
Example [1, 2, 1]: a window that never needs to shrink. The interesting behavior here is the count climb — re-picking a type that already owns a basket.
Why it is correct: two facts close the argument. best can never overstate the optimum, because it only ever reads a legal window (the while loop runs before every measurement). And the optimal window is never missed: let [L, R] be a legal run of the maximum length. The left edge only advances while the current window holds three types — and during any shrink that reaches L, the window is exactly the legal optimum [L, R], so the loop condition fails there and the left edge never passes L. When the right edge finishes reading R, the measured window is [left, R] with left <= L, hence at least as long as [L, R], and best catches R - L + 1.
Why it is linear: the right edge adds each tree exactly once and the left edge removes each tree at most once, so every counter increment and decrement is paid for by one of those two events — O(n) total work. The counter holds at most two types in any legal window, and only three transiently during a shrink, so the extra space is a constant independent of n: O(n) time, O(1) space. This is optimal, since the whole row must be read at least once.