Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Fruit Into Baskets

MEDIUMProblemSolveExternal Links

Description

You are visiting a fruit farm where trees are arranged in a single row. Each tree bears a specific type of fruit, represented by an integer in the array fruits, where fruits[i] is the fruit type of the i-th tree.

You carry exactly two baskets, and each basket can hold only one type of fruit (but unlimited quantity of that type). Starting from any tree of your choice, you must pick exactly one fruit from every consecutive tree moving to the right — you cannot skip any tree. You must stop when you encounter a tree whose fruit type cannot fit into either basket (meaning it would be a third distinct type).

Return the maximum number of fruits you can collect by choosing the best starting tree.

Examples

Example 1

Input: fruits = [1, 2, 1]

Output: 3

Explanation: All three trees contain only two distinct fruit types (1 and 2). One basket holds type 1, the other holds type 2. We can start from tree 0 and pick all three fruits without encountering a third type.

Example 2

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

Output: 3

Explanation: If we start from tree 0, we pick type 0 and type 1, but at tree 2 we encounter type 2 — a third type — so we stop with only 2 fruits. Instead, starting from tree 1 lets us pick [1, 2, 2] — only two types (1 and 2) — collecting 3 fruits. No starting position yields more than 3.

Example 3

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

Output: 4

Explanation: Starting from tree 1, we pick fruits [2, 3, 2, 2] — using one basket for type 2 and another for type 3 — giving us 4 fruits. Starting from tree 0 would hit a third type (3) at index 2, yielding only 2 fruits.

Constraints

  • 1 ≤ fruits.length ≤ 10^5
  • 0 ≤ fruits[i] < fruits.length

Editorial

Brute Force

Intuition

The most straightforward approach is to try every possible starting tree and see how many consecutive fruits we can collect before running into a third distinct type.

Imagine walking down the row of trees with your two baskets. At each tree you start from, you walk forward, putting each fruit into the matching basket. The moment you find a fruit that matches neither basket (a third type), you stop, note how many fruits you collected, and walk back to try the next starting tree.

For each starting index i, we maintain a set of fruit types seen so far. We expand j rightward, adding each fruit type to the set. Once the set has more than 2 types, we stop and record the length j − i.

Step-by-Step Explanation

Let's trace through Example 3: fruits = [1, 2, 3, 2, 2].

Step 1: Start from i = 0. Begin collecting.

Step 2: j = 0, fruit type 1. Baskets: {1}. One type, plenty of room. Length = 1.

Step 3: j = 1, fruit type 2. Baskets: {1, 2}. Both baskets now in use. Length = 2.

Step 4: j = 2, fruit type 3. Three distinct types! We only have 2 baskets, so stop. Record length = 2 for starting position 0. max_fruits = 2.

Step 5: Start from i = 1. j = 1, fruit type 2. Baskets: {2}. One type.

Step 6: j = 2, fruit type 3. Baskets: {2, 3}. Two types — baskets full but valid. Length = 2.

Step 7: j = 3 and j = 4, both fruit type 2. Already in baskets. Expand all the way to the end. Length = 4. max_fruits = 4.

Step 8: Starting positions i = 2, 3, 4 yield lengths 3, 2, 1 respectively — none beats 4.

Result: max_fruits = 4.

Brute Force — Trying Every Starting Tree — Watch how the brute force fixes a starting tree, scans rightward tracking distinct fruit types, and stops when a third type appears.

Algorithm

  1. Initialize max_fruits = 0
  2. For each starting index i from 0 to n − 1:
    a. Create an empty set of fruit types
    b. For each index j from i to n − 1:
    • Add fruits[j] to the set
    • If the set has more than 2 types, break
    • Update max_fruits = max(max_fruits, j − i + 1)
  3. Return max_fruits

Code

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int n = fruits.size();
        int maxFruits = 0;
        for (int i = 0; i < n; i++) {
            unordered_set<int> types;
            for (int j = i; j < n; j++) {
                types.insert(fruits[j]);
                if (types.size() > 2) break;
                maxFruits = max(maxFruits, j - i + 1);
            }
        }
        return maxFruits;
    }
};
class Solution:
    def totalFruit(self, fruits: list[int]) -> int:
        n = len(fruits)
        max_fruits = 0
        for i in range(n):
            types = set()
            for j in range(i, n):
                types.add(fruits[j])
                if len(types) > 2:
                    break
                max_fruits = max(max_fruits, j - i + 1)
        return max_fruits
class Solution {
    public int totalFruit(int[] fruits) {
        int n = fruits.length;
        int maxFruits = 0;
        for (int i = 0; i < n; i++) {
            Set<Integer> types = new HashSet<>();
            for (int j = i; j < n; j++) {
                types.add(fruits[j]);
                if (types.size() > 2) break;
                maxFruits = Math.max(maxFruits, j - i + 1);
            }
        }
        return maxFruits;
    }
}

Complexity Analysis

Time Complexity: O(n²)

The outer loop runs n times, and for each iteration the inner loop can scan up to n elements. In the worst case (such as an array with only 1 or 2 fruit types), every inner loop scans to the end, giving n × n = O(n²) operations.

Space Complexity: O(1)

The set tracks at most 3 fruit types at any point (the third triggers a break). Since the set size is bounded by a constant, the space is O(1) regardless of input size.

Why This Approach Is Not Efficient

With n up to 10^5, the brute force may perform up to 10^10 operations — far too slow for competitive time limits.

The root of the inefficiency is repeated scanning. When we move from starting position i to i+1, we discard all the information we gathered and re-scan many of the same elements. But observe: as the starting position moves right, the farthest valid ending position can only stay the same or move right — it never jumps backwards.

This monotonicity property is the hallmark of a sliding window problem. Instead of restarting the scan each time, we can maintain a window that grows from the right and shrinks from the left. To efficiently track how many distinct fruit types are inside the window, we use a hash map that stores each type's count. When a type's count reaches zero, we remove it from the map. The number of distinct types is simply the size of the map.

This eliminates all redundant work, reducing time from O(n²) to O(n).

Bar chart comparing O(n²) brute force with O(n) sliding window operations for n = 100,000
Bar chart comparing O(n²) brute force with O(n) sliding window operations for n = 100,000

Optimal Approach - Sliding Window with Hash Map

Intuition

Instead of restarting from scratch at each tree, we maintain a flexible window [left, right] that slides across the array. The window always satisfies one rule: it contains at most 2 distinct fruit types.

Picture yourself walking along the row of trees carrying a clipboard. On the clipboard you track which fruit types are in your two baskets and how many of each. You keep moving forward (expanding right), picking fruits. The moment your clipboard shows 3 types, you start removing fruits from the left end of your collection — dropping them until one type is completely gone and you are back to 2 types.

A hash map serves as the clipboard: keys are fruit types, values are how many of each type are in the current window. When we shrink the window from the left, we decrement the count of the departing fruit. When a count hits zero, we delete that key — representing that type leaving the baskets entirely.

Both the left and right pointers move only forward. Each element is added to the window exactly once (by right) and removed at most once (by left). Total work: at most 2n pointer movements, giving O(n) time.

Step-by-Step Explanation

Let's trace through Example 3: fruits = [1, 2, 3, 2, 2].

Step 1: Expand right to index 0. Fruit type 1. Add to hash map: {1: 1}. One distinct type. Window [0..0], length 1. max_fruits = 1.

Step 2: Expand right to index 1. Fruit type 2. Hash map: {1: 1, 2: 1}. Two types — baskets full. Window [0..1], length 2. max_fruits = 2.

Step 3: Expand right to index 2. Fruit type 3. Hash map now has 3 keys: {1: 1, 2: 1, 3: 1}. Three types — overflow! Must shrink from left.

Step 4: Shrink: remove fruits[left=0] = type 1. Decrement count to 0, so delete type 1 from map. Hash map: {2: 1, 3: 1}. left = 1. Two types — valid again. Window [1..2], length 2.

Step 5: Expand right to index 3. Fruit type 2. Increment count: {2: 2, 3: 1}. Still 2 types. Window [1..3], length 3. max_fruits = 3.

Step 6: Expand right to index 4. Fruit type 2. Increment: {2: 3, 3: 1}. Still 2 types. Window [1..4], length 4. max_fruits = 4.

Step 7: All trees processed. max_fruits = 4.

Sliding Window — Expand and Shrink with Two Baskets — Watch the sliding window expand to include trees and shrink when a third fruit type appears, always maintaining at most 2 distinct types in the window.

Algorithm

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

Code

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        unordered_map<int, int> count;
        int left = 0, maxFruits = 0;
        for (int right = 0; right < fruits.size(); right++) {
            count[fruits[right]]++;
            while (count.size() > 2) {
                int leftFruit = fruits[left];
                count[leftFruit]--;
                if (count[leftFruit] == 0) {
                    count.erase(leftFruit);
                }
                left++;
            }
            maxFruits = max(maxFruits, right - left + 1);
        }
        return maxFruits;
    }
};
class Solution:
    def totalFruit(self, fruits: list[int]) -> int:
        count = {}
        left = 0
        max_fruits = 0
        for right in range(len(fruits)):
            fruit = fruits[right]
            count[fruit] = count.get(fruit, 0) + 1
            while len(count) > 2:
                left_fruit = fruits[left]
                count[left_fruit] -= 1
                if count[left_fruit] == 0:
                    del count[left_fruit]
                left += 1
            max_fruits = max(max_fruits, right - left + 1)
        return max_fruits
class Solution {
    public int totalFruit(int[] fruits) {
        Map<Integer, Integer> count = new HashMap<>();
        int left = 0, maxFruits = 0;
        for (int right = 0; right < fruits.length; right++) {
            count.merge(fruits[right], 1, Integer::sum);
            while (count.size() > 2) {
                int leftFruit = fruits[left];
                count.merge(leftFruit, -1, Integer::sum);
                if (count.get(leftFruit) == 0) {
                    count.remove(leftFruit);
                }
                left++;
            }
            maxFruits = Math.max(maxFruits, right - left + 1);
        }
        return maxFruits;
    }
}

Complexity Analysis

Time Complexity: O(n)

Despite the nested while loop, the total work is linear. The right pointer visits each element exactly once (n iterations). The left pointer also visits each element at most once over the entire run — it only moves forward and can travel at most n positions total. Each hash map operation (insert, delete, lookup) is O(1) on average. Therefore, total operations ≤ 2n, which simplifies to O(n).

Space Complexity: O(1)

The hash map stores at most 3 entries at any moment (briefly 3 before the while loop reduces it back to 2). Since this is a constant bound independent of n, the space complexity is O(1). The remaining variables (left, maxFruits) are also constant space.