Fruit Into Baskets

Medium Arrays & Hashing Sliding Window · Variable Original on LeetCode

Fruit Into Baskets is a medium arrays & hashing problem solved with the sliding window · variable pattern. The best approach, optimal (sliding window with counts), runs in O(n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (try every start) up.

Problem

A row of trees is described by the array fruits, where fruits[i] is the kind of fruit growing on tree i. You have two baskets, and each basket may hold only one kind of fruit (but any amount of it).

You choose any tree to start from and then move strictly to the right, picking exactly one fruit from every tree you pass, including the first. You must stop as soon as you reach a tree whose fruit fits in neither basket. Return the maximum number of fruits you can collect.

Examples

Example 1

Input
fruits = [3, 3, 1, 3, 2, 2, 1]
Output
4
Why
Starting at index 0 you can pick 3, 3, 1, 3 (two kinds) before kind 2 shows up.

Example 2

Input
fruits = [0, 4, 4, 0, 4, 2]
Output
5
Why
The first five trees only hold kinds 0 and 4.

Example 3

Input
fruits = [3, 1, 2, 0]
Output
2
Why
Every three neighbouring trees already contain three different kinds, so the best is any two adjacent trees.

Constraints

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

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (try every start)O(n²)O(1)
Optimal (sliding window with counts)O(n)O(n)

1Brute force (try every start)

TimeO(n²)Each of the n starts may walk up to n trees.
SpaceO(1)The set never holds more than three kinds.

For every starting tree, walk right while the set of kinds seen so far has at most two members. Record the longest walk.

  1. For each start i, keep a small set of kinds.
  2. Move j from i to the right, adding fruits[j]; stop as soon as the set would grow to three.
  3. Update the best with j - i.
class Solution {
    public int totalFruit(int[] fruits) {
        int n = fruits.length, best = 0;
        for (int i = 0; i < n; i++) {
            int a = -1, b = -1, j = i;
            while (j < n) {
                int f = fruits[j];
                if (f == a || f == b) { j++; continue; }
                if (a == -1) a = f;
                else if (b == -1) b = f;
                else break;
                j++;
            }
            best = Math.max(best, j - i);
        }
        return best;
    }
}

2Optimal (sliding window with counts)

TimeO(n)Both pointers only move right, so each tree enters and leaves the window once.
SpaceO(n)A count array indexed by kind (kinds are below n); a hash map with at most three keys works too.

Grow a window [left, right] one tree at a time and keep a count for each kind inside it. Whenever a third kind enters, move left forward, decrementing counts and dropping kinds that reach zero, until only two kinds remain. The largest window seen is the answer.

  1. Keep an array count indexed by kind and a counter kinds of kinds with a positive count.
  2. For each right: increment count[fruits[right]]; if it became 1, kinds++.
  3. While kinds > 2: decrement count[fruits[left]]; if it became 0, kinds--; left++.
  4. best = max(best, right - left + 1).
class Solution {
    public int totalFruit(int[] fruits) {
        int n = fruits.length;
        int[] count = new int[n];
        int kinds = 0, left = 0, best = 0;
        for (int right = 0; right < n; right++) {
            if (count[fruits[right]]++ == 0) kinds++;
            while (kinds > 2) {
                if (--count[fruits[left]] == 0) kinds--;
                left++;
            }
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

Edge cases to test

  • A single tree: the answer is 1
  • All trees hold the same kind: take the whole row
  • Every tree holds a different kind: the answer is 2 (or 1 if there is only one tree)
  • The best window is at the very end of the row

Hints

Hint 1

Once you start, you walk right until a third kind appears. So the answer is the longest contiguous stretch containing at most two distinct values.

Hint 2

Use a sliding window with a count per kind. When the window holds three kinds, shrink it from the left until one kind's count drops to zero.

FAQ

What is the best time complexity for Fruit Into Baskets?

Optimal (sliding window with counts) runs in O(n) time and O(n) extra space. Both pointers only move right, so each tree enters and leaves the window once.

Which pattern does Fruit Into Baskets use?

It is a arrays & hashing problem that uses the sliding window · variable pattern. Other problems with the same pattern: Minimum Size Subarray Sum, Count of Subarrays with Product Less Than K, Longest Repeating Character Replacement.

Is there a brute force solution for Fruit Into Baskets?

Yes. Brute force (try every start) takes O(n²) time and O(1) space. For every starting tree, walk right while the set of kinds seen so far has at most two members.

Which edge cases should I test for Fruit Into Baskets?

A single tree: the answer is 1; All trees hold the same kind: take the whole row; Every tree holds a different kind: the answer is 2 (or 1 if there is only one tree); The best window is at the very end of the row.