☕ DSA Java Articles

Topics › Sliding Window and Two Pointers › Medium Problems

Fruit Into Baskets

Medium TUF ID 926 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

A row of trees is described by an array fruits, where fruits[i] is the type of fruit tree i produces. You have two baskets, and each basket can hold any amount of fruit but only of one type. You pick a starting tree and then move right, picking exactly one fruit from every tree, until you reach a tree whose fruit fits in neither basket. Return the maximum number of fruits you can collect.

Strip away the story and the task is: find the longest contiguous subarray that contains at most two distinct values. The starting tree is the left end of the subarray, and you stop just before the first tree that would introduce a third type.

Constraints: 1 ≤ n ≤ 10^5, 0 ≤ fruits[i] < n.

Example 1

fruits = [1, 2, 3, 2, 2]
answer = 4          // start at index 1: types 2 and 3 cover [2, 3, 2, 2]

Example 2

fruits = [3, 3, 3, 1, 2, 1, 1, 2, 3, 3, 4]
answer = 5          // [1, 2, 1, 1, 2] at indices 3..7 uses only types 1 and 2

Approach 1: Brute force

Intuition. Try every starting tree. From that start, walk right and add each type to a set. As soon as the set reaches three types, the walk from this start is over: every longer subarray from the same start also has three types. The longest walk over all starts is the answer.

Algorithm.

  1. For each start i, create an empty set types.
  2. For j = i ..: add fruits[j]. If the set size exceeds 2, break. Otherwise update best with j - i + 1.
  3. Return best.
static int bruteForce(int[] fruits) {
    int n = fruits.length, best = 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;           // a third type: no longer window from i can work
            best = Math.max(best, j - i + 1);
        }
    }
    return best;
}

Complexity. Time O(n^2): an array with only two types never triggers the break. Space O(1): the set never holds more than three values.

Approach 2: Better, shrinking sliding window

Intuition. “At most two distinct types” is a monotonic property. If a window satisfies it, so does every window inside it; if a window violates it, so does every window containing it. So we can keep a single window [l, r] and only ever move both edges to the right.

A set is no longer enough, because when we drop fruits[l] from the left we need to know whether another copy of that type is still inside the window. So we keep a count per type in a map. A type leaves the map only when its count reaches zero, which means count.size() is exactly the number of distinct types in the window.

Algorithm.

  1. l = 0, empty map count, best = 0.
  2. For each r: increment count[fruits[r]].
  3. While the map has more than two keys: decrement count[fruits[l]], remove the key if it hits zero, and increment l.
  4. Update best with r - l + 1.
static int better(int[] fruits) {
    Map<Integer, Integer> count = new HashMap<>();
    int l = 0, best = 0;
    for (int r = 0; r < fruits.length; r++) {
        count.merge(fruits[r], 1, Integer::sum);
        while (count.size() > 2) {
            int f = fruits[l];
            if (count.merge(f, -1, Integer::sum) == 0) count.remove(f);
            l++;
        }
        best = Math.max(best, r - l + 1);
    }
    return best;
}

Map.merge(key, delta, Integer::sum) adds delta to the stored count (or stores delta if the key is absent) and returns the new count, which lets us test for zero in the same line.

Complexity. Time O(2n): every index enters the window once and leaves it at most once, and the map operations are O(1) because the map never holds more than three keys. Space O(1) for the same reason.

Approach 3: Optimal, the window that never shrinks

Intuition. We only want the maximum length. Suppose the best valid window seen so far has length L. Shrinking the window below L cannot help us find something longer. So when the third type arrives, we do not shrink until the window is valid; we drop exactly one fruit from the left, so the window slides right while keeping its length. While it is invalid we simply do not record it. If some later valid window is longer, the right edge will reach it with the window back at two types and the length goes up by one.

The effect is that the inner while becomes an if: at most one left-step per right-step.

Algorithm.

  1. Same setup as Approach 2.
  2. For each r: increment count[fruits[r]].
  3. If the map has more than two keys: remove one occurrence of fruits[l] and increment l.
  4. If the map now has at most two keys, update best with r - l + 1.
static int optimal(int[] fruits) {
    Map<Integer, Integer> count = new HashMap<>();
    int l = 0, best = 0;
    for (int r = 0; r < fruits.length; r++) {
        count.merge(fruits[r], 1, Integer::sum);
        if (count.size() > 2) {                    // slide: drop exactly one fruit from the left
            int f = fruits[l];
            if (count.merge(f, -1, Integer::sum) == 0) count.remove(f);
            l++;
        }
        if (count.size() <= 2) best = Math.max(best, r - l + 1);
    }
    return best;
}

Dry run on fruits = [1, 2, 3, 2, 2]:

r add count after add slide? l valid? best
0 1 {1:1} no 0 yes 1
1 2 {1:1, 2:1} no 0 yes 2
2 3 {1:1, 2:1, 3:1} drop 1 1 yes, {2:1, 3:1} 2
3 2 {2:2, 3:1} no 1 yes 3
4 2 {2:3, 3:1} no 1 yes 4

Complexity. Time O(n): one pass with constant work per tree. Space O(1): at most three keys in the map.

Because 0 ≤ fruits[i] < n, you can also replace the map with an int[n] count array plus a distinct counter. That avoids boxing and is noticeably faster in Java, at the price of O(n) space. The map version is shown because it works for any value range.

Edge cases and pitfalls