Fruit Into Baskets

SLIDING WINDOW · MEDIUM

Builds on Day 5: Sliding Window Pattern

The optimal solution below is a variable-size (“grow and shrink”) window over a frequency map — read that lesson first if the two-pointer expand/shrink mental model is still new.

The problem

You’re walking a row of fruit trees, given as an array fruits where fruits[i] is the type of fruit growing at position i. You’re carrying exactly 2 baskets, and each basket can hold only one type of fruit — but an unlimited quantity of that type. Starting from any tree, you must pick fruit from every tree you pass as you walk in one direction, and you have to stop the moment you’d need a third basket for a third type. Return the maximum total number of fruits you can collect.

Strip away the orchard framing and this is exactly “longest contiguous subarray containing at most 2 distinct values” — a specific case (K=2) of a well-known general pattern. For example, fruits=[1,2,1] → 3 (all three trees, only 2 types present). fruits=[0,1,2,2] → 3 (the run [1,2,2] — starting at tree 0 would force a third type at tree 2). fruits=[1,2,3,2,2] → 4 (the run [2,3,2,2], trees 1 through 4).

Solution 1: Brute force — check every subarray with a fresh Set

The most direct reading of the problem: try every possible contiguous run of trees. For each candidate subarray [i..j], build a brand-new Set from its contents and check how many distinct fruit types it holds. If that count is at most 2, it’s a legal run — compare its length against the best one seen so far. There’s no cleverness here, just an exhaustive check of every window and how many types it contains.

fruits = [1, 2, 3, 2, 2] — expected answer: 4 (the run [2, 3, 2, 2] at indices 1–4)

Press play to run the brute force algorithm.

current best: —

Step 0 / 17

▶ Play — O(n³)↺ Reset

The code

function totalFruitBrute(fruits) {
  const n = fruits.length;
  let best = 0;

  for (let i = 0; i < n; i++) {
    for (let j = i; j < n; j++) {
      const types = new Set(fruits.slice(i, j + 1));
      if (types.size <= 2) {
        best = Math.max(best, j - i + 1);
      }
    }
  }
  return best;
}

Line by line:

• The two nested loops enumerate every possible (i, j) start/end pair — every contiguous subarray of fruits, O(n²) of them total.
• fruits.slice(i, j + 1) copies out the subarray, and new Set(...) collapses it down to its distinct values — both O(n) operations, run fresh for every single (i, j) pair with no reuse of work from the previous pair.
• if (types.size <= 2) is the entire correctness check: at most 2 distinct fruit types fit in 2 baskets, so any subarray failing this is simply skipped.
• best = Math.max(best, j - i + 1) only updates when the subarray both qualifies and beats the current record — no early exit, no memory of previous subarrays’ contents.

Complexity

Time	Space	Approach
O(n³)	O(n)	O(n²) subarrays, each requiring a fresh O(n) Set build to count distinct types

Solution 2: Optimal — variable-size sliding window with a frequency map

Instead of re-examining every subarray from scratch, slide a window across the array exactly once. Maintain a Map that counts how many of each fruit type currently sit inside the window [left..right]. Expand right one tree at a time, adding to the map. The moment the map holds more than 2 distinct types (map.size > 2), the window has become illegal — shrink from left, decrementing counts and deleting any type whose count hits zero, until the map is back down to at most 2 keys. After every expansion (and any shrinking it triggered), the window [left..right] is guaranteed valid, so its length is a candidate for the best answer.

The reason this is O(n) rather than O(n²) is the classic amortized sliding-window argument: right moves forward exactly once per outer iteration, n times total across the whole run. left only ever moves forward too — it never resets or steps backward — so across the entire algorithm it can advance at most n times as well. Two pointers, each doing at most n forward steps total, gives O(n) + O(n) = O(n) overall, not O(n) work repeated for every position of right.

fruits = [1, 2, 3, 2, 2] — same array as brute force, watch the window shrink once then grow back to the same best answer of 4

Press play to run the optimal algorithm.

distinct types in window: —

Step 0 / 18

▶ Play — O(n)↺ Reset

The code

function totalFruitOptimal(fruits) {
  const count = new Map();
  let left = 0;
  let best = 0;

  for (let right = 0; right < fruits.length; right++) {
    const type = fruits[right];
    count.set(type, (count.get(type) || 0) + 1);

    while (count.size > 2) {
      const leftType = fruits[left];
      const next = count.get(leftType) - 1;
      if (next === 0) {
        count.delete(leftType);
      } else {
        count.set(leftType, next);
      }
      left++;
    }

    best = Math.max(best, right - left + 1);
  }
  return best;
}

Line by line:

• count is a Map from fruit type → how many of that type sit inside the current window [left..right].
• count.set(type, (count.get(type) || 0) + 1) adds the newly-included tree at right to the map — this always runs, every iteration, before any shrinking is considered.
• while (count.size > 2) — not if — because a single left-step might remove a type’s last copy and still leave the map at 3 keys if, hypothetically, more than one type needed clearing; a while guarantees the window is fully legal before moving on. (In this specific problem one shrink step always suffices, since only one new type can appear per expansion, but while is the version that generalizes correctly and is what an interviewer would expect.)
• if (next === 0) count.delete(leftType) — deleting the key, not just leaving a zero count sitting in the map, is what keeps count.size an honest measure of “distinct types currently present.” A stale zero-count entry would make size lie.
• best = Math.max(best, right - left + 1) runs once per outer iteration, after any shrinking — at this point the window is always guaranteed valid (≤ 2 distinct types), so every measurement here is a legitimate candidate.

Complexity

Time	Space	Approach
O(n)	O(1)	Variable-size sliding window — right and left each advance forward at most n times total; the frequency map never holds more than 3 keys

Complexity comparison

Solution	Time	Space
Brute force (every subarray, fresh Set)	O(n³)	O(n)
Optimal (sliding window + frequency map)	O(n)	O(1)

This is a dramatic, real complexity gap, not a same-technique relabeling. The brute force redoes O(n) work — building a whole new Set — for every one of O(n²) candidate subarrays. The sliding window replaces that with two pointers that only ever move forward, each doing at most n total steps across the entire run, and a frequency map that stays bounded at 2–3 keys regardless of how large fruits is — O(n²) time collapses to a single pass, and O(n) space collapses to O(1) because the map’s size is capped by the problem’s own “2 baskets” constraint, not by the input length.

Interview corner

Q: This problem is often described as “longest substring with at most K distinct characters, for K=2.” What changes if the interviewer generalizes it to K distinct types instead of exactly 2?

• Almost nothing about the algorithm’s shape changes — the same expand-right, shrink-left-while-over-limit structure works unmodified. The only edit is the shrink condition: while (count.size > K) instead of > 2.
• The complexity story is identical too: still O(n) time, since both pointers still only move forward, and still O(K) space, since the map is capped at K+1 keys at any instant (K existing types plus the one just added, right before a shrink brings it back down).
• Recognizing that “2 baskets” is just K=2 of a general pattern — rather than a special-cased trick — is exactly the kind of connection that signals real pattern understanding instead of memorized solutions to individual LeetCode problems.

Q: Why is while (count.size > 2) safe to write as a loop that could in principle run multiple times per outer iteration, without breaking the claimed O(n) time complexity?

• The amortized argument doesn’t care how the shrink work is distributed across outer iterations — it only cares about the total number of times left moves, summed over the entire run.
• Since left only ever increases and is bounded above by n (it can never pass right, which itself never exceeds n - 1), it can advance at most n times total across every iteration of the outer loop combined — regardless of whether those n steps happen one at a time or in occasional bursts.
• That’s the standard “each pointer does at most n units of forward-only work, across the whole algorithm” argument — it’s what makes two nested-looking loops still sum to O(n), not O(n²), and it’s worth being able to state explicitly rather than just asserting “it’s O(n), trust me.”

Q: Why does the optimal solution delete a key from the map the instant its count hits zero, instead of just leaving a 0 value sitting there?

• The whole shrink condition, count.size > 2, depends on size meaning “number of distinct types actually present in the window right now.” A key with a stale 0 count would still count toward .size, even though that type isn’t really in the window anymore.
• Leaving zero-count entries around would make the algorithm shrink far too eagerly (or fail to detect that a window is actually valid), producing a wrong answer — not just wasted work.
• count.delete(leftType) is what keeps the map’s size an honest, minimal representation of “which types are currently between left and right,” which is exactly the invariant the shrink loop relies on.

Q: Trick question — the frequency map here is built with a real Map. Would swapping it for a plain object change anything, given that fruit types in this problem are always small integers?

const obj = {};
obj[1] = 'from a number key';
obj['1'] = 'from a string key';
console.log(Object.keys(obj).length);   // ?

const map = new Map();
map.set(1, 'from a number key');
map.set('1', 'from a string key');
console.log(map.size);                  // ?

• Answer: Object.keys(obj).length is 1, but map.size is 2 — not matching counts.
• A plain object coerces every key to a string, so the property written by obj[1] = ... and the one written by obj['1'] = ... are the exact same property — the second write silently overwrites the first.
• A Map never coerces keys — the number 1 and the string '1' are distinct keys, so both entries exist independently and size correctly reports 2.

Trap

For this exact problem it happens to be harmless either way, since LeetCode’s fruits array elements are always plain numbers, never a mix of numbers and numeric strings — so an object-based frequency map would give the same answer here. But it’s the general, correctness-relevant reason a Map is the right default tool for “count distinct keys of arbitrary type” rather than an object: an object’s implicit string-coercion is a silent correctness hazard the moment key types could ever mix, while Map has no such gotcha to reason about in the first place.

Quiz

Quiz 1: This problem is a specific case of a well-known general pattern. Which one?

Longest subarray/substring with at most K distinct values, with K fixed at 2.

Fruit Into Baskets is exactly “longest substring with at most K distinct characters/values” with K fixed at 2 — the “2 baskets, 1 type each” framing is just a concrete story wrapped around a general sliding-window pattern.

Quiz 2: What specifically makes the brute-force solution O(n³) rather than O(n²)?

Every one of the O(n²) subarrays triggers a fresh O(n) Set build, with no work reused between overlapping subarrays.

Every one of the O(n²) (i, j) subarray pairs triggers its own fresh fruits.slice(i, j+1) plus new Set(...) — an O(n) operation repeated for every pair, with zero reuse of work between overlapping subarrays. That’s what turns O(n²) subarrays into O(n³) total work.

Quiz 3: The optimal solution has an inner while loop nested inside a for loop. Why is the overall time still O(n), not O(n²)?

left only ever moves forward and never resets, so across the whole run it advances at most n times total — same bound as right.

left never resets and never steps backward — across the ENTIRE run it advances at most n times total, same as right. Two pointers each doing at most n forward steps overall sums to O(n), not O(n) work repeated for every position of right.

Quiz 4: Why does the optimal solution call count.delete(leftType) instead of just leaving that entry at count 0?

A stale 0-count entry would still count toward count.size, breaking the shrink condition’s meaning and producing wrong answers.

count.size is what the shrink condition depends on to mean “distinct types actually present.” A key left at count 0 would still count toward .size even though that type isn’t really in the window — deleting it is what keeps the invariant correct, not just tidy.

Quiz 5: Why is the optimal solution’s space complexity O(1) rather than O(n), even though it uses a Map that could in principle grow?

The map’s size is capped by the “at most 2 types” constraint itself — it never holds more than 2–3 keys, regardless of input length.

The frequency map’s size is capped by the problem’s own constraint (at most 2 valid types, plus momentarily a 3rd right before a shrink corrects it) — bounded at 2–3 keys no matter how large fruits grows. That’s what makes the optimal solution O(1) space, not O(n) like the brute force’s Set.