Fruit Into Baskets
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^50 <= 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.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
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.
| Approach | Time | Space |
|---|---|---|
| Brute force (try every start) | O(n²) | O(1) |
| Optimal (sliding window with counts) | O(n) | O(n) |
1Brute force (try every start)
O(n²)Each of the n starts may walk up to n trees.O(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.
- For each start i, keep a small set of kinds.
- Move j from i to the right, adding fruits[j]; stop as soon as the set would grow to three.
- 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;
}
}class Solution:
def totalFruit(self, fruits: List[int]) -> int:
n, best = len(fruits), 0
for i in range(n):
a = b = -1
j = i
while j < n:
f = fruits[j]
if f != a and f != b:
if a == -1:
a = f
elif b == -1:
b = f
else:
break
j += 1
best = max(best, j - i)
return bestclass Solution {
public:
int totalFruit(vector<int>& fruits) {
int n = fruits.size(), 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 = max(best, j - i);
}
return best;
}
};function totalFruit(fruits) {
const n = fruits.length;
let best = 0;
for (let i = 0; i < n; i++) {
let a = -1, b = -1, j = i;
while (j < n) {
const 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)
O(n)Both pointers only move right, so each tree enters and leaves the window once.O(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.
- Keep an array
countindexed by kind and a counterkindsof kinds with a positive count. - For each right: increment count[fruits[right]]; if it became 1, kinds++.
- While kinds > 2: decrement count[fruits[left]]; if it became 0, kinds--; left++.
- 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;
}
}class Solution:
def totalFruit(self, fruits: List[int]) -> int:
count = [0] * len(fruits)
kinds = left = best = 0
for right, f in enumerate(fruits):
if count[f] == 0:
kinds += 1
count[f] += 1
while kinds > 2:
count[fruits[left]] -= 1
if count[fruits[left]] == 0:
kinds -= 1
left += 1
best = max(best, right - left + 1)
return bestclass Solution {
public:
int totalFruit(vector<int>& fruits) {
int n = fruits.size();
vector<int> count(n, 0);
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 = max(best, right - left + 1);
}
return best;
}
};function totalFruit(fruits) {
const n = fruits.length;
const count = new Array(n).fill(0);
let kinds = 0, left = 0, best = 0;
for (let 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.