AlgoMaster Logo

Fruit Into Baskets

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

Strip away the fruit tree story, and this problem is asking: find the longest contiguous subarray that contains at most 2 distinct values. The "two baskets" represent two allowed distinct types, "moving to the right" means the subarray must be contiguous, and "maximum number of fruits" means we want the longest such subarray.

So if fruits = [1, 2, 3, 2, 2], we need to find the longest subarray with at most 2 different numbers. The subarray [2, 3, 2, 2] (indices 1 through 4) has types 2 and 3, which is 2 distinct values, and its length is 4. That is the answer.

This is a sliding window problem. We need a window that expands as long as it contains at most 2 distinct fruit types, and shrinks when a third type enters. The core challenge is tracking how many distinct types are in the current window at any moment.

Key Constraints:

  • 1 <= fruits.length <= 10^5: With up to 100,000 elements, we need O(n) or O(n log n). An O(n^2) solution that checks every subarray would mean up to 10 billion operations, which is too slow.
  • 0 <= fruits[i] < fruits.length: Fruit types are non-negative integers bounded by the array length. This means we could use an array instead of a hash map for counting, but a hash map is cleaner and generalizes better.

Approach 1: Brute Force

Intuition

Try every possible starting position, and from each one, walk to the right collecting fruit until a third distinct type appears. Track the maximum distance reached.

For each starting index i, we expand to the right while keeping count of how many distinct fruit types we have seen. The moment we hit a third type, we stop. The number of fruits collected from index i is the length of that subarray. We do this for every i and take the maximum.

Algorithm

  1. Initialize maxFruits = 0.
  2. For each starting index i from 0 to n - 1:
    • Create a set to track distinct fruit types in the current subarray.
    • Walk from index i to the right, adding each fruit type to the set.
    • If the set size exceeds 2, stop.
    • Update maxFruits with the number of elements collected.
  3. Return maxFruits.

Visualization and Code

Loading animation...

The bottleneck is redundant scanning. After walking from index i to index j, the next iteration starts at i + 1 and re-scans most of the same elements. The next approach removes this duplication by sliding a single window forward instead of rebuilding it from scratch at every start.

Approach 2: Sliding Window with Hash Map

Intuition

Instead of trying every starting position independently, we maintain a window [left, right] that always contains at most 2 distinct fruit types. We expand right one step at a time, and when we encounter a third type, we shrink from the left until we are back to 2 types. The maximum window size across all valid states is our answer.

To know when the window holds more than 2 types, we track how many of each fruit type it currently contains. A hash map from fruit type to its count handles this. Moving right forward increments the count of the new fruit. Moving left forward decrements the count of the fruit being left behind, and when that count drops to 0 we remove its key from the map. The number of keys in the map is the number of distinct types in the window.

Algorithm

  1. Initialize left = 0, maxFruits = 0, and an empty hash map countMap.
  2. For each right from 0 to n - 1:
    • Add fruits[right] to countMap (increment its count).
    • While countMap has more than 2 keys (more than 2 distinct types):
      • Decrement the count of fruits[left] in the map.
      • If the count reaches 0, remove that key from the map.
      • Increment left.
    • Update maxFruits = max(maxFruits, right - left + 1).
  3. Return maxFruits.

Visualization and Code

Loading animation...

This approach runs in O(n) time, but every step performs hash map lookups and updates, which carry overhead from hashing and collision handling. Because at most 2 types are ever allowed, the next approach drops the map and tracks the two types in plain variables.

Approach 3: Sliding Window Without Hash Map

Intuition

Since we only allow 2 distinct types, we can track those two types explicitly without a hash map. We maintain two variables for the two fruit types currently in the window, and a third variable secondTypeStart that records where the most recent contiguous block of the same fruit type started.

When a third type arrives, the new left boundary becomes secondTypeStart, and we drop whichever type is not part of the most recent run. Instead of shrinking one element at a time, left jumps directly to its new position in a single step.

Algorithm

  1. If n <= 2, return n (any array of length at most 2 has at most 2 types).
  2. Initialize left = 0, maxFruits = 0, secondTypeStart = 0, typeA = fruits[0], typeB = -1. Here typeA and typeB are the two types currently allowed in the window.
  3. For each right from 0 to n - 1, in this order:
    • If fruits[right] is a third type (not typeA and not typeB), and typeB has already been set, jump left to the current secondTypeStart (this evicts the older type). Then set typeA = fruits[right - 1] and typeB = fruits[right].
    • After the eviction check, if fruits[right] differs from fruits[right - 1], set secondTypeStart = right to record the start of this new run.
    • Update maxFruits = max(maxFruits, right - left + 1).
  4. Return maxFruits.

The eviction check must run before the secondTypeStart update. When a third type arrives, left jumps to where the most recent run started, which is the value secondTypeStart held coming into this iteration, not right itself.

Visualization and Code

Loading animation...