Skip to main content
DSA patterns

Fruit Into Baskets

mediumSliding windowGoogleSwiggyZomato

Problem statement

You're walking along a row of fruit trees. Each tree produces one type of fruit, given as fruits[i], an integer id for that type. You carry exactly two baskets, and each basket can hold only one fruit type — but as much of it as you like.

Starting from any tree you choose, you must pick exactly one fruit from every tree as you move to the right, without skipping any. You stop the moment you reach a tree whose fruit type doesn't fit in either basket.

Return the largest number of fruits you can collect this way. Because you can't skip a tree, the trees you visit always form one unbroken stretch — so this is really asking: what's the longest contiguous stretch of trees that contains at most 2 distinct fruit types?

Examples

Example 1

Input: fruits = [1,2,1]

Output: 3

Explanation: All 3 trees use only two fruit types (1 and 2), so you

Example 2

Input: fruits = [0,1,2,2]

Output: 3

Explanation: Starting from index 1 gives [1,2,2], which uses only types

Example 3

Input: fruits = [1,2,3,2,2]

Output: 4

Explanation: Starting from index 1 gives [2,3,2,2], which uses only

Hints

Hint 1: Because you can't skip a tree, the trees you end up picking always form one unbroken stretch — and that stretch can contain at most 2 different fruit types.

Approach

Optimal: Track each type's last-seen index, jump instead of shrinking

Intuition

The Better approach's shrink loop can take several steps in a row, because it only removes one tree at a time and has to wait for a type's count to hit zero. There's a shortcut: instead of counting how many of each type are in the window, just remember the last index where each type was seen. The moment a 3rd type shows up, you already know exactly which type to drop — the one that hasn't been seen in the longest time — and exactly where the new window should start: right after that type's last occurrence. No loop is needed, because everything before that index is guaranteed to belong only to the type being dropped or to something even older, so nothing valid is skipped.

This is what makes it faster in practice than the Better approach: every step does one lookup and, at most, one direct jump — never a run of several shrink steps in a row.

Steps

  1. Start with left = 0, an empty map last_seen (fruit type → its most recent index), and best = 0.
  2. For each right from 0 to n - 1:
    1. Record last_seen[fruits[right]] = right.
    2. If last_seen now holds more than 2 distinct types:
      • Find the type whose last-seen index is smallest (the one used longest ago).
      • Set left to one past that index.
      • Remove that type from last_seen.
    3. Update best with right - left + 1.
  3. Return best.

Dry run

fruits = [1, 2, 3, 2, 2]

right fruit last_seen after recording evicted type (oldest) new left window size best
0 1 {1: 0} — 0 1 1
1 2 {1: 0, 2: 1} — 0 2 2
2 3 {1: 0, 2: 1, 3: 2} 1 (last seen at 0) 1 2 2
3 2 {2: 3, 3: 2} — 1 3 3
4 2 {2: 4, 3: 2} — 1 4 4

The window ends up covering indices 1..4, exactly [2, 3, 2, 2] — matching the example's explanation.

Edge cases: a single-tree row returns 1 immediately, since last_seen never exceeds one entry. A row using only one or two fruit types in total never triggers an eviction, so left stays at 0 the whole way and the answer is the full length of the row.

flowchart LR A[Record this tree's type and index] --> B{More than 2 distinct types now?} B -- yes --> C[Evict the type with the oldest last-seen index; jump left just past it] B -- no --> D[Update best with the current window size] C --> D D --> E[Move right forward by one] E --> A

Complexity

Time O(n) - each tree is looked at exactly once. Instead of a variable number of shrink steps, an overflowing window is fixed with a single direct jump, checked against at most 3 stored entries — a constant amount of work per tree.

Space O(1) - the map holds at most 3 entries (fruit type → its last-seen index) at any moment.

class Solution:
    def totalFruit(self, fruits: list[int]) -> int:
        last_seen: dict[int, int] = {}
        left = 0
        best = 0
        for right, fruit in enumerate(fruits):
            last_seen[fruit] = right
            if len(last_seen) > 2:
                evict_type = min(last_seen, key=last_seen.get)
                left = last_seen[evict_type] + 1
                del last_seen[evict_type]
            best = max(best, right - left + 1)
        return best


if __name__ == "__main__":
    print(Solution().totalFruit([1, 2, 1]))          # 3
    print(Solution().totalFruit([0, 1, 2, 2]))       # 3
    print(Solution().totalFruit([1, 2, 3, 2, 2]))    # 4
RecapThe whole problem in a few lines, for the night before
  • Spot it: longest subarray with at most 2 distinct values
  • Idea: variable window with a small count map; when a third type enters, move the left edge until only two types remain
  • Cost: O(n) time, O(1) space (at most 3 keys)
  • Trap: delete a key from the map when its count drops to zero, or the distinct count will be wrong

Interview follow-ups

  • What if there were k baskets instead of exactly 2?

    Change every > 2 check to > k in either approach — the algorithm and its O(n) time complexity don't otherwise change. The map can now briefly hold up to k + 1 entries instead of 3, so space becomes O(k) instead of O(1).

  • Return the actual range of tree indices for the best window, not just its length.

    Track bestLeft and bestRight alongside best, and update all three together whenever a new best window is found: bestLeft = left, bestRight = right. At the end, the best stretch of trees is fruits[bestLeft : bestRight + 1].

  • The row of trees streams in and doesn't fit in memory. How would you adapt this?

    Both sliding-window approaches already process one tree at a time and only ever keep a small map alongside the two pointers — nothing about them requires the whole row up front. Feed trees in one at a time exactly as they arrive; memory stays O(distinct types in the window), which is at most 3, regardless of how long the stream runs.

Frequently asked questions

The basket rule says only 2 fruit types can be carried at once, and the "pick from every tree, don't skip" rule means the trees you visit always form one unbroken stretch. Put those two rules together and you get exactly this: find the longest contiguous stretch of the array that uses at most 2 distinct values.

Everything at or before the evicted type's last-seen index belongs either to that type itself or to something even older that's no longer relevant — the two types you're keeping both have their most recent occurrence after that index, by definition of "oldest last-seen index" being the one chosen for eviction. So nothing that still matters gets skipped, and no valid, longer window could have started any earlier than that.

The same shape shows up when scanning a stream of events for the longest stretch that only touches a small number of things at once — for example, the longest run of consecutive log lines that mention at most two service names, or the longest window of a canary rollout during which traffic only ever hit two versions of a feature flag.

Both approaches generalize directly: replace "more than 2 distinct types" with "more than k distinct types" everywhere. The frequency-map approach's shrink loop and the last-seen approach's eviction step both work exactly the same way, just compared against k instead of a fixed 2.