Generated by Codex with GPT-5

Quick facts

What the problem is really asking

The story sounds specific, but the core problem is simple:

find the length of the longest contiguous subarray that contains at most two distinct values.

Each tree produces exactly one fruit type. The picker starts somewhere, walks to the right, and must keep every fruit in one of two baskets. That means the picked segment has to stay contiguous, and it can contain only two fruit types at a time.

So this is not really a greedy “choose the two most common fruits” problem. It is a window problem where the valid window condition is:

the current segment contains at most two distinct fruit types

The first correct idea

A straightforward approach is to try every starting index, expand to the right, and stop as soon as a third fruit type appears.

That works, and it matches the problem statement directly, but it can take O(n^2) time in the worst case because many overlapping segments get scanned again and again.

That repeated work is the clue that a sliding window should exist.

Why sliding window is the right tool

This problem has the exact structure that sliding window likes:

  • the answer is a longest contiguous segment
  • there is a simple validity rule for a segment
  • once a segment becomes invalid, moving its left edge to the right is the only way to fix it

Suppose a window already contains three fruit types. Extending it farther right will never make it valid again, because the old three types are still inside. The only repair move is to shrink from the left until one type disappears.

That gives the optimal strategy:

  1. Move the right pointer one tree at a time and add that fruit to the window.
  2. Track how many of each fruit type are inside the window.
  3. If the window now contains more than two distinct types, move the left pointer rightward until the window is valid again.
  4. After every repair, update the best window length seen so far.

Each index enters the window once and leaves once, so the total work is linear.

How to derive the optimal solution in an interview

A clean interview progression is:

  1. Rephrase the story as “longest subarray with at most two distinct values.”
  2. Notice that validity depends only on the current window, not on the full history.
  3. Observe that if a window is invalid, shrinking from the left is the only useful move.
  4. Use a frequency map so the algorithm always knows when a fruit type has completely left the window.

That last detail matters. It is not enough to remember the two current basket types. The algorithm must also know when one fruit type’s count drops to zero so it can be removed from the active set.

Why the algorithm is correct

The key invariant is:

the window between left_index and right_index is always the longest valid window that ends at right_index after the repair step finishes.

When the right pointer advances, the window may become invalid by introducing a third fruit type. Shrinking from the left until only two types remain produces the only valid window ending at that right_index that could possibly lead to the best answer, because any earlier left boundary would still include too many types.

So once the window is repaired, its length is the best answer for windows ending at that position. Taking the maximum over all positions gives the overall optimum.

Best approach

For this exact problem, the standard frequency-map sliding window is the best general answer:

  • Time: O(n)
  • Space: O(1) for this problem’s fixed basket limit, or more generally O(k) for the “at most k distinct values” version

The implementation is short, easy to justify, and generalizes immediately to common interview follow-ups.

Python solution

The implementation below uses a frequency map to maintain the current window. When a third fruit type appears, it removes trees from the left until only two types remain. The helper function keeps the main LeetCode entry point small while preserving production-quality naming and structure.

from collections import defaultdict
from typing import DefaultDict, List


def longest_window_with_at_most_two_fruit_types(fruits: List[int]) -> int:
    """
    Return the length of the longest contiguous segment containing
    at most two distinct fruit types.
    """
    fruit_counts_in_window: DefaultDict[int, int] = defaultdict(int)
    left_index = 0
    best_window_length = 0

    for right_index, fruit_type in enumerate(fruits):
        fruit_counts_in_window[fruit_type] += 1

        # Repair the window until it satisfies the "two baskets" rule again.
        while len(fruit_counts_in_window) > 2:
            left_fruit_type = fruits[left_index]
            fruit_counts_in_window[left_fruit_type] -= 1

            if fruit_counts_in_window[left_fruit_type] == 0:
                del fruit_counts_in_window[left_fruit_type]

            left_index += 1

        current_window_length = right_index - left_index + 1
        best_window_length = max(best_window_length, current_window_length)

    return best_window_length


class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        """LeetCode entry point."""
        return longest_window_with_at_most_two_fruit_types(fruits)

Interview follow-ups

What changes if the interviewer gives you k baskets instead of 2?

Almost nothing changes. The same sliding-window pattern still works if the validity rule becomes “at most k distinct fruit types.” The only code change is replacing the condition len(fruit_counts_in_window) > 2 with len(fruit_counts_in_window) > k. The reason this generalizes so cleanly is that the core property stays the same: once a window has too many distinct values, only shrinking from the left can make it valid again. The time complexity remains O(n) because each element still enters and leaves the window at most once, while the auxiliary space becomes O(k) because the map stores the fruit types currently inside the window.

Can you return the actual segment, not just its length?

Yes. Keep two extra variables for the best window boundaries, such as best_start_index and best_end_index, and update them whenever a longer valid window is found. Nothing else about the sliding-window logic changes. This works because the algorithm already visits every candidate optimal window exactly when it becomes valid after the repair step. The complexity stays O(n) time, and the extra space stays the same. The tradeoff is only a small amount of extra bookkeeping.

Can you solve this without a hash map?

For this exact problem, yes, because the basket limit is fixed at 2. There is a clever constant-state solution that tracks the current fruit type, the previous fruit type, the length of the trailing run of the current fruit, and the current valid window length. When a new fruit matches one of the two active types, the window extends. When it introduces a third type, the new window must start at the beginning of the trailing run plus the new fruit, because that is the longest suffix containing only two types. This works because with only two allowed types, the suffix of repeated last fruit is exactly the part that can be preserved when a third type arrives. It still runs in O(n) time and uses O(1) extra space, but it is less obvious and harder to derive under interview pressure than the frequency-map version.

What if the trees arrive as a stream and memory is tight?

If the full array is not available up front, the answer depends on which version of the algorithm is used. The frequency-map sliding window normally relies on reading fruits[left_index] while shrinking, so it assumes the current window contents are still accessible. In a streaming setting, the constant-state two-type solution becomes more attractive because it only keeps summary information about the active window rather than the whole segment. That makes it a better fit for true streaming when the basket count stays fixed at 2. The tradeoff is flexibility: the compact state trick is specialized, while the frequency-map window adapts much more naturally to the general “k baskets” variant.