DSA sheet · Arrays · Sliding Window pattern

Fruits Into Baskets

This problem hides a sliding window inside a story about a farm. Once you see through the story, it asks: "what is the longest subarray with at most 2 different values?" The teacher first writes a brute force that restarts from every tree with a fresh hashmap. She explains where to restart after getting stuck, and why a hashmap with counts is needed instead of a set. Then she turns it into a sliding window that shrinks from the left instead of restarting.

Why it matters: this is the first window in the sheet whose rule is about how many distinct values are inside, so the window's "summary" is a frequency map instead of a sum. The same shape solves Longest Substring with K Unique Characters and is the building block of Subarrays with K Different Integers.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting (sliding window, frequency maps)
• Part A · Brute force: start at every tree, fresh map each time
• Part B · Optimal: sliding window with a frequency map
• Part C · Revision page

Part 0 · Before starting

What is a subarray?

A subarray is a piece of the array whose elements are next to each other (contiguous): a start index, an end index, and everything in between, with nothing skipped. (In a string, the same thing is a substring.) Its length is end − start + 1. In this problem, "picking fruit from consecutive trees" is exactly choosing a subarray.

The brute force over all windows, and why it repeats work

Two loops can try every start and stretch to the right from it: O(n²). The waste: if we stretch from index 0 over [1, 1, 2] and get stuck, the next start (index 1) re-adds 1 and 2, which we had already put into our map. Sliding window keeps what's already in the window and only fixes the edges.

The window [left..right]: expand and shrink

A window is the current subarray between two pointers, left and right. We keep a summary of what's inside so we don't re-scan it.

• Expansion phase (done by right): move right forward and add the new element to the summary.
• Shrinking phase (done by left): remove nums[left] from the summary and move left forward.

Both pointers start at index 0 and only ever move forward.

Fixed-size vs variable-size windows

Longest vs shortest vs count

For "exactly K different values" (problem 8 in this sheet) the trick is exactly(K) = atMost(K) − atMost(K − 1). This problem is already an "at most 2", so we don't need it.

Why the rule must be monotonic

Sliding window works only if adding an element can only make the window worse or equal, and removing one can only make it better or equal. Here the rule is "at most 2 distinct values": adding a tree can only keep or increase the number of types, and removing one can only keep or decrease it. So it's safe. (For sums this is why numbers must be positive. A negative number would break it.)

Frequency maps (dict / Counter)

A frequency map stores value → how many times it appears (in the window). In Python: a dict with freq.get(x, 0) + 1, or collections.Counter / defaultdict(int). len(freq) is the number of distinct values, as long as we delete keys whose count drops to 0.

freq = {}
for x in [1, 1, 2, 1]:
    freq[x] = freq.get(x, 0) + 1     # {1: 3, 2: 1} -> 2 distinct types
freq[2] -= 1                         # {1: 3, 2: 0}
if freq[2] == 0:
    del freq[2]                      # {1: 3} -> now len(freq) == 1

The teacher uses Java's map.getOrDefault(key, 0) + 1, which is the same as Python's freq.get(key, 0) + 1. One more tool, only for Sliding Window Maximum: the monotonic deque, which we don't need here.

The teacher's 4 array patterns

Part A · Brute force: start at every tree, fresh map each time

LeetCode 904

1The question in simple words

A farm has one row of fruit trees, left to right. fruits[i] is the type of fruit on tree i (a number). You want to collect as many fruits as possible, but the owner has rules:

• You have only 2 baskets.
• Each basket holds only one type of fruit, but any amount of it.
• You may start at any tree, then take exactly one fruit from every tree as you walk right. You can't skip a tree and you can't turn back.
• When you reach a tree whose fruit fits neither basket (a third type), you must stop.

Return the most fruits you can pick.

The teacher notices: since the rule is about counting types, a hashmap will probably help. She comes back to that soon.

2What the constraints tell us

• 1 ≤ n ≤ 10⁵. O(n²) would be 10¹⁰, way beyond ~10⁸ → TLE. We'll need O(n). Brute force first anyway.
• 0 ≤ fruits[i] < n. Types go up to about 10⁵, which fits easily in an int. No negatives (that matters later, when she rules out Kadane's).
• n ≥ 1, so there's always at least one tree, and the answer is at least 1.

3Intuition: try every starting tree

Stand at a tree, walk right picking fruit, and keep track of which types are in the baskets. When a third type shows up, stop and note how many fruits you got. Then try again from the next tree. The best of all these tries is the answer.

4Building the logic from examples

Walk it on [1, 2, 3, 2, 2]

Start at index 0: take 1 (basket A), take 2 (basket B) → 2 fruits. Next is 3, a third type → stop. Best so far: 2.

Where do we restart: at the 3 where we got stuck, or at the next tree after the old start?

The teacher asks this on purpose. Restarting at the 3 (index 2) looks tempting, because we stopped there. But then the best we'd find is [3, 2, 2] = 3 fruits. The real best is [2, 3, 2, 2] = 4, which starts at index 1, before the 3. So the brute force must restart at old start + 1, not where it got stuck.

What do we store the baskets in?

"How many different types do I have?" is a question about unique values. For unique values we normally reach for a set or a hashmap. The teacher picks a hashmap (type → count). For the brute force alone, a set would also do (we never take anything out). But the count will be essential once we start removing fruits in Part B, so she uses the map from the start. Her set vs map example is explained in Part B.

Building the inner loop

• Put fruits[right] in the map: if the type is new, its count becomes 1; if it's there, add 1. (Java's getOrDefault, Python's get(x, 0) + 1.)
• Then check: is len(map) > 2? If yes, this tree is a third type → break (and don't count it).
• Otherwise this fruit fits → count += 1.

After the inner loop ends (by break or by reaching the end), update ans = max(ans, count).

5Approach steps

1. ans = 0.
2. For every start left: new empty map, count = 0.
3. For right from left to the end: add fruits[right] to the map.
4. If the map has more than 2 types → break. Else count += 1.
5. After the inner loop: ans = max(ans, count).
6. Return ans.

6Code (Python)

class Solution:
    def totalFruit(self, fruits):
        n = len(fruits)
        ans = 0
        for left in range(n):                    # try every starting tree
            basket = {}                          # fresh baskets: type -> count
            count = 0                            # fruits picked from this start
            for right in range(left, n):
                f = fruits[right]
                basket[f] = basket.get(f, 0) + 1
                if len(basket) > 2:              # a third type: must stop
                    break
                count += 1
            ans = max(ans, count)
        return ans

7Code line by line

8Dry run (hand table)

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

Final answer: 4 ✓. Notice how start 1 re-added 2 and start 2 re-added 3, 2, 2: the repeated work the sliding window removes.

9Complexity & remember

• Time O(n²): left goes over all n trees, and for every left, right restarts at left and can run nearly to the end. With n = 10⁵ that's ~10¹⁰ → not acceptable.
• Space O(1): the map never holds more than 3 keys.

Part B · Optimal: sliding window with a frequency map

LeetCode 904

1The question again, with the new goal

Same question: the longest run of consecutive trees with at most 2 types. Goal: O(n), with left never restarting.

2Choosing the pattern

• Two pointers ✗: used when only two particular points matter and nothing between them. Here every tree between the two ends matters.
• Prefix sum ✗: for continuous sums between two indexes, typically to answer many range-sum queries. We're not summing anything.
• Kadane's ✗: for maximum sums with negative numbers. The values go from 0 up to 10⁵, no negatives.
• Sliding window ✓: we care about two points and everything between them.

3Intuition: don't restart, just drop trees from the left

Look at [1, 1, 2, 3, 3]. The brute force goes 1, 1, 2, gets stuck at 3, then restarts at index 1 and re-adds 1 and 2, which were already in the map. Why recompute them?

Sliding window's idea instead:

• Expand: keep moving right while the baskets hold at most 2 types (the condition is true).
• When a third type arrives (the condition becomes false), don't throw everything away. Shrink: move left forward, removing those fruits from the baskets, until only 2 types are left (the condition is true again).
• Then record the length and expand again.

On [1, 1, 2, 3, 3]: when 3 arrives, the window is [1, 1, 2, 3] with 3 types. Drop the first 1 → [1, 2, 3], still 3 types. Drop the second 1 → [2, 3], 2 types ✓. Stop shrinking. Then right picks up the last 3 → [2, 3, 3], length 3.

4Building the logic from examples

Why a hashmap with counts, not a set (her [1, 1, 2, 1, 3] example)

Say the window is [1, 1, 2, 1] and the next tree is 3. Now we must shrink from the left until there are only 2 types.

The window is now [1, 3], and type 1 is still needed (one 1 is still inside). A set can only say "is 1 present: yes/no", so removing one 1 removes the whole type. The map knows how many 1s are inside, so the type only disappears when its count reaches 0. That's why the frequency count is required.

The shrinking step, piece by piece

With a sum we "removed" by subtracting. Here we "added" by increasing a count, so we remove by decreasing it:

1. basket[fruits[left]] -= 1 (one fewer of that type).
2. If that count is now 0, delete the key: the type is completely gone from the window.
3. left += 1.

Recording the answer

After the while loop, the window is valid again (≤ 2 types), so ans = max(ans, right − left + 1). This is a "longest valid window" problem, so we record after shrinking.

5Approach steps

1. left = 0, ans = 0, empty map basket (made once, before the loop).
2. For each right: add fruits[right] to the map (expand).
3. While the map has more than 2 types: decrease the count of fruits[left], delete it if 0, left += 1 (shrink).
4. ans = max(ans, right − left + 1).
5. Return ans.

6Code (Python)

class Solution:
    def totalFruit(self, fruits):
        basket = {}                              # type -> how many in the window
        left = 0
        ans = 0
        for right in range(len(fruits)):
            f = fruits[right]
            basket[f] = basket.get(f, 0) + 1     # expand: pick this fruit
            while len(basket) > 2:               # third type: shrink from the left
                g = fruits[left]
                basket[g] -= 1
                if basket[g] == 0:
                    del basket[g]                # type completely gone
                left += 1
            ans = max(ans, right - left + 1)     # window is valid again
        return ans

7Code line by line

8Dry run

fruits = [1, 2, 3, 2, 2] (the teacher's example).

The array at the key moments (yellow = window, grey = left behind):

Final answer: 4 ✓, matching the brute force. In step 3 the window shrank by one tree and kept 2 and 3. The brute force would have thrown everything away and started again.

A second picture, her [1, 1, 2, 1, 3] example, where the shrink needs three removals:

For [1, 1, 2, 1, 3] the best answer is 4 ([1, 1, 2, 1]), recorded at step 4, before the 3 arrived.

9Complexity & remember

• Time O(n): right moves from 0 to n − 1 once. The while inside looks like it makes it O(n²), but left never goes back to the start. It also moves forward only, touching each index at most once in the whole run. So the total is n + n = O(2n) = O(n). Each map operation is O(1).
• Space O(1): the map holds at most 3 types at any moment (2, plus the one that triggers a shrink).

She shows the final code accepted as one of the fastest solutions.

Part C · Revision page

s = Solution()
print(s.totalFruit([1, 2, 1]))                    # 3
print(s.totalFruit([0, 1, 2, 2]))                 # 3
print(s.totalFruit([1, 2, 3, 2, 2]))              # 4
print(s.totalFruit([3, 3, 3, 1, 2, 1, 1, 2, 3, 3, 4]))  # 5
print(s.totalFruit([1, 1, 1]))                    # 3  (one type is fine)
print(s.totalFruit([0, 1, 2, 3]))                 # 2  (all different)
print(s.totalFruit([7]))                          # 1

Based on this video: Fruits Into Baskets | Sliding Window