Fruit Into Baskets Solution In C++/Java/Python/JS
Problem Description:
You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are represented by an integer array fruits where fruits[i] is the type of fruit the ith tree produces.
You want to collect as much fruit as possible. However, the owner has some strict rules that you must follow:
- You only have two baskets, and each basket can only hold a single type of fruit. There is no limit on the amount of fruit each basket can hold.
- Starting from any tree of your choice, you must pick exactly one fruit from every tree (including the start tree) while moving to the right. The picked fruits must fit in one of your baskets.
- Once you reach a tree with fruit that cannot fit in your baskets, you must stop.
Given the integer array fruits, return the maximum number of fruits you can pick.
Examples:
Input: fruits = [1,2,1]
Output: 3
Explanation: We can pick from all 3 trees.
Input: fruits = [0,1,2,2]
Output: 3
Explanation: We can pick from trees [1,2,2].
If we had started at the first tree, we would only pick from trees [0,1].
Input: fruits = [1,2,3,2,2]
Output: 4
Explanation: We can pick from trees [2,3,2,2].
If we had started at the first tree, we would only pick from trees [1,2].
Constraints:
- 1 <= fruits.length <= 105
- 0 <= fruits[i] < fruits.length
Brute Force Approach
Imagine walking along a long line of fruit trees. Each tree gives only one type of fruit. You have two baskets, and you can only collect one type of fruit in each basket. As you walk, you want to collect as many fruits as possible, but you cannot pick up a third type. Your goal? Find out the longest stretch of trees from which you can collect fruit using just your two baskets.
Building Intuition:
When you first see this type of problem, it helps to look for patterns. For example:
- If you have to pick fruits from trees of only two types, what happens if you see a tree of a third type?
- You can’t pick it unless you drop all fruits of one type already in your baskets!
- You want the longest consecutive stretch (subarray) of trees that contain only two different fruits.
Ask yourself:
How can I keep track of which fruits I am collecting right now?
How do I know when I need to stop, or when I can keep going?
To start, we can approach the problem by considering each index in the array as a potential starting point for collecting fruits. From that index, we move forward and try to collect as many fruits as possible while making sure we only pick from at most two types.
For every such starting point, we calculate the length of the valid subarray (the continuous segment where we’re allowed to pick fruits), and we keep track of the maximum length found so far. This way, by the end of the process, we will have found the longest subarray that contains only two different types of fruits.
But how do we determine whether the subarray starting at index i is valid, and how long it can be?
Starting from index i, we simply walk forward through the array, collecting fruits. We continue this process as long as the number of distinct fruit types we've seen remains less than or equal to two.
As soon as we encounter a third type, we stop collecting. The number of fruits collected up to that point is the length of the current valid subarray. We then compare it with the answer (ans) and update our answer if it's larger.
How to keep track of fruit types while collecting them?
To keep track of the fruit types we’re collecting, we can use a set. A set is useful here because it stores unique elements, which allows us to easily monitor how many different types of fruits we’ve collected so far.
For every fruit we see, we add its type to the set. If the size of the set ever becomes greater than 2, it means we've encountered a third type, and that’s our signal to stop. At that point, we update the result with the maximum length found so far and move on to the next starting index.
Finally, we will have our updated answer (ans). We simply return it.
Fruit Into Baskets Example
Input: fruits = [1,2,1,2,3]
Output: 4
Explanation: We can pick from trees [1, 2, 1, 2].
Initial Values:
- n = 5
- res = 0
Outer Loop Iteration i = 0:
- types = {}
- j = 0: types = {1} → valid (size = 1)
- j = 1: types = {1, 2} → valid (size = 2)
- j = 2: types = {1, 2} → valid (2 already exists)
- j = 3: types = {1, 2} → valid
- j = 4: fruits[4] = 3, now types = {1, 2, 3} → size = 3 → break
- res = max(0, 4) = 4
Outer Loop Iteration i = 1:
- types = {}
- j = 1: types = {2}
- j = 2: types = {1, 2}
- j = 3: types = {1, 2}
- j = 4: types = {1, 2, 3} → break
- res = max(4, 3) = 4
Outer Loop Iteration i = 2:
- types = {}
- j = 2: types = {1}
- j = 3: types = {1, 2}
- j = 4: types = {1, 2, 3} → break
- res = max(4, 2) = 4
Outer Loop Iteration i = 3:
- types = {}
- j = 3: types = {2}
- j = 4: types = {2, 3}
- j = 5: out of bounds
- res = max(4, 2) = 4
Outer Loop Iteration i = 4:
- types = {}
- j = 4: types = {3}
- j = 5: out of bounds
- res = max(4, 1) = 4
Final Result: return 4;
The maximum number of fruits collected in two baskets = 4
(from subarray [1, 2, 1, 2])
Fruit Into Baskets Solution
Step 1: Initialize variables:
- Create a variable to store the size of the array.
- Create a result variable to store the maximum number of fruits collected.
Step 2: Start an outer loop:
Loop over each index in the array as a potential starting point for collecting fruits.
Step 3: Initialize a set inside the outer loop:
This set will keep track of the types of fruits collected in the current subarray.
Step 4: Start an inner loop from the current index:
Keep moving forward as long as the number of fruit types in the set is less than or equal to 2.
Step 5: Insert fruit types into the set:
For each fruit, add it to the set and continue only if the total types do not exceed two.
Step 6: Stop the inner loop:
Break the inner loop if adding a fruit makes the set contain more than two types.
Step 7: Update the result:
After the inner loop ends, calculate the length of the current valid subarray and update the result if it’s the largest so far.
Step 8: Return the result:
After checking all starting points, return the maximum length found.
Fruit Into Baskets Solution
Fruit Into Baskets solution in C++
class Solution {
public:
int totalFruit(vector<int>& fruits) {
int n = fruits.size(); // Total number of trees
int res = 0; // Variable to store the maximum number of fruits collected
// Try starting the collection from each index
for (int i = 0; i < n; i++) {
unordered_set<int> types; // To store unique fruit types
int j = i;
// Continue collecting until there are more than 2 types
while (j < n && (types.size() < 2 || types.count(fruits[j]))) {
types.insert(fruits[j]); // Add the current fruit type to the set
j++; // Move to the next tree
}
// Update the maximum result found so far
res = max(res, j - i);
}
return res;
}
};
Fruit Into Baskets solution in Java
class Solution {
public int totalFruit(int[] fruits) {
int n = fruits.length, res = 0;
// Try starting from each tree
for (int i = 0; i < n; i++) {
Set<Integer> types = new HashSet<>();
int j = i;
// Collect fruits until there are more than 2 types
while (j < n && (types.size() < 2 || types.contains(fruits[j]))) {
types.add(fruits[j]);
j++;
}
// Update max fruits collected
res = Math.max(res, j - i);
}
return res;
}
}Fruit Into Baskets solution in Python
class Solution:
def totalFruit(self, fruits: List[int]) -> int:
n = len(fruits)
res = 0
# Try starting from each index
for i in range(n):
types = set()
j = i
# Keep collecting as long as we have <= 2 types
while j < n and (len(types) < 2 or fruits[j] in types):
types.add(fruits[j])
j += 1
# Update maximum result
res = max(res, j - i)
return resFruit Into Baskets solution in JavaScript
/**
* @param {number[]} fruits
* @return {number}
*/
var totalFruit = function(fruits) {
let n = fruits.length, res = 0;
// Try starting from each index
for (let i = 0; i < n; i++) {
let types = new Set();
let j = i;
// Collect fruits while we have at most 2 types
while (j < n && (types.size < 2 || types.has(fruits[j]))) {
types.add(fruits[j]);
j++;
}
// Update max result
res = Math.max(res, j - i);
}
return res;
}Fruit Into Baskets Complexity Analysis
Time Complexity: O(n2)
The brute-force solution checks every possible starting point and expands the window forward until more than 2 fruit types are found.
Structure of the Code
- Outer loop: Runs n times (once for each starting index i)
- Inner loop: For each i, pointer j can move from i up to n, but with set insertions and size checks
Time Complexity Breakdown
- Outer loop → O(n)
- Inner loop:
- In the worst case, the inner loop may go up to the end of the array for each i (if all fruits are the same or only 2 types for long stretches).
- Each iteration involves:
- set.insert() → O(1) average (since it's an unordered_set)
- set.size() and set.count() → O(1) average
- So the worst-case inner loop per iteration: O(n)
- Therefore:
Total Time Complexity: O(n²)
Because for each of the n starting positions, the inner loop may take up to n steps.
Space Complexity: O(n)
Auxiliary Space Complexity:
This includes all the extra space used during execution, excluding the input and output themselves.
Components:
- unordered_set<int> types:
- Stores up to 3 elements at most (since loop breaks at 3 types)
- So, space = O(1)
- Loop counters and variables like i, j, n, res:
- Constant space → O(1)
Auxiliary Space Complexity = O(1)
(No significant dynamic memory used; all storage is constant-sized.)
Input and Output Complexity
Input:
- vector<int>& fruits — passed by reference.
- Takes O(n) space (but not counted in auxiliary space).
Output:
- A single integer → O(1) space
Total Space Complexity
= Auxiliary Space + Input Space + Output Space
= O(1) + O(n) + O(1)
= O(n)
Is the brute force approach efficient?
The time complexity of the brute-force solution is O(n²). According to the problem constraints, the input size n can go up to 10⁵. This means the total number of operations in the worst case would be 10⁵ × 10⁵ = 10¹⁰, which is far too large to process efficiently.
Typically, we can handle up to 10⁷ operations per second in competitive programming or real-time execution. Since our brute-force approach may require significantly more than that, it becomes computationally infeasible for large inputs.
Therefore, the brute-force method is not optimal, and we need to explore a more efficient approach.
Optimal Approach
Intuition:
In the brute-force solution, we considered each index as a starting point and tried to find the maximum subarray starting from that index where the number of fruit types was at most 2.
This meant that for every index i, we would iterate forward to find a range j such that the subarray from i to j contained at most two distinct fruit types. This results in a time complexity of O(n²).
Key Observation for Optimisation
Let’s say for a certain starting point i, we found that the subarray from index i to index j is valid (i.e., it contains at most 2 types of fruits). Now, in the brute-force approach, we would repeat the whole process again, starting from i + 1.
But there's an important observation:
If the subarray from i to j is valid, then the subarray from i + 1 to` must also be valid — since it contains fewer elements and still includes only the same fruit types.
So instead of starting over each time, we can reuse part of the previous result and avoid unnecessary recomputation.
We can make use of two pointers, which will depict a "window". A window will contain a valid subarray of fruits. Two pointers, typically called l (left) and r (right), will represent the current window or subarray we are evaluating.
- The right pointer (r) keeps expanding the window to include new fruits.
- The left pointer (l) is used to shrink the window from the left whenever the window becomes invalid (i.e., more than two fruit types are in the window).
This way, we slide the window across the array while maintaining the condition that only two types of fruits can be present. This type of approach of using pointers l and r to depict a window, is called a sliding window approach.
How Do We Track Fruit Types?
What we need is something that will help keep uniqueness. Because we want all the unique elements in our subarray. The total number of unique elements will give us the count of the total number of fruit types in a subarray from l to r.
We can use a map (or dictionary) where:
- The key is the fruit type.
- The value is the count of that fruit type within the current window.
Every time we move the right pointer (r), we:
- Add the fruit at index r to the map or increment its count.
If the map size becomes greater than 2, it means we now have more than 2 types of fruits in the current window, and the window is no longer valid. To fix this, we:
- Move the left pointer (l) forward.
- For each fruit at index l, we decrement its count in the map.
- If a fruit's count becomes zero, we remove it from the map.
- We continue this process until the map has at most 2 fruit types again.
To keep track of the answer, we can simply use a variable "total" which will keep track of the number of elements in our current window.
- Increasing r will the "total" as the window size increases by 1.
- Increasing l will decrease "total" as the window size decreases by 1.
Animation Fruits into Baskets - Optimal Solution
Fruit Into Baskets Example
Initial Setup
- count = {} → stores count of fruit types in the current window
- l = 0 → left pointer
- total = 0 → number of fruits in current window
- res = 0 → result (maximum fruits collected)
Iteration 1: r = 0 → fruit = 1
- Add fruit 1: count = {1: 1}, total = 1
- count.size() = 1 → OK (≤ 2)
- Update res = max(0, 1) = 1
Iteration 2: r = 1 → fruit = 2
- Add fruit 2: count = {1: 1, 2: 1}, total = 2
- count.size() = 2 → OK
- Update res = max(1, 2) = 2
Iteration 3: r = 2 → fruit = 1
- Add fruit 1: count = {1: 2, 2: 1, total = 3
- count.size() = 2 → OK
- Update res = max(2, 3) = 3
Iteration 4: r = 3 → fruit = 2
- Add fruit 2: count = {1: 2, 2: 2}, total = 4
- `count.size() = 2 → OK
- Update res = max(3, 4) = 4
Iteration 5: r = 4 → fruit = 3
- Add fruit 3: count = {1: 2, 2: 2, 3: 1}, total = 5
- count.size() = 3 → Invalid, need to shrink window
Shrinking Window from Left
- Left fruit = fruits[l] = fruits[0] = 1
- Decrement count of 1: count = {1: 1, 2: 2, 3: 1}, total = 4
- Still 3 types → move l = 1
- Left fruit = fruits[1] = 2
- Decrement count of 2: count = {1: 1, 2: 1, 3: 1}, total = 3
- Still 3 types → move l = 2
- Left fruit = fruits[2] = 1
- Decrement count of 1: count = {1: 0, 2: 1, 3: 1}, total = 2
- Now count[1] == 0, erase it: count = {2: 1, 3: 1}
- Now count.size() = 2 → Valid again
- l = 3
Final Step
- Update res = max(4, 2) = 4
Final : Return: 4
Fruit Into Baskets Algorithm
Step 1: Initialize required variables
- Create a map/dictionary (e.g., count) to store the frequency of each fruit type in the current window.
- Initialize two pointers:
- l (left pointer) = 0 → marks the start of the window
- r (right pointer) → will iterate through the array
- Initialize:
- total to store the number of fruits in the current valid window
- res to store the result (maximum number of fruits collected)
Step 2: Start iterating with the right pointer
- Use a loop from r = 0 to the end of the fruits array.
- For each fruit:
- Add or update the fruit count in the map.
- Increase the total number of fruits in the window.
Step 3: Check if the window is valid
- After adding a fruit, check if the map has more than two types of fruits:
- If yes, the window is invalid and must be shrunk from the left.
Step 4: Shrink the window from the left
- While the map contains more than 2 types:
- Subtract one fruit from count[fruits[l]]
- Decrease total since we're removing a fruit
- If a fruit count becomes 0, remove it from the map
- Move the left pointer (l) forward
Step 5: Update the result
- After ensuring the window is valid (at most 2 types), update res with the maximum value of res and total.
Step 6: Return the result
- After the loop ends, return res as the maximum number of fruits that can be collected from any valid subarray.
Fruit Into Baskets leetcode solution
Fruit Into Baskets solution in C++
class Solution {
public:
int totalFruit(vector<int>& fruits) {
unordered_map<int, int> count; // Stores frequency of fruit types in current window
int l = 0, total = 0, res = 0;
for (int r = 0; r < fruits.size(); r++) {
count[fruits[r]]++; // Add current fruit to map
total++;
// If more than 2 fruit types, shrink window from left
while (count.size() > 2) {
int f = fruits[l];
count[f]--;
total--;
// Remove fruit type if count is 0
if (count[f] == 0) count.erase(f);
l++;
}
// Update maximum fruits collected
res = max(res, total);
}
return res;
}
};Fruit Into Baskets solution in Java
class Solution {
public int totalFruit(int[] fruits) {
Map<Integer, Integer> count = new HashMap<>(); // Map to store fruit type frequencies
int l = 0, total = 0, res = 0;
for (int r = 0; r < fruits.length; r++) {
// Add current fruit
count.put(fruits[r], count.getOrDefault(fruits[r], 0) + 1);
total++;
// Shrink window if there are more than 2 types
while (count.size() > 2) {
int f = fruits[l];
count.put(f, count.get(f) - 1);
total--;
if (count.get(f) == 0) count.remove(f);
l++;
}
// Update max result
res = Math.max(res, total);
}
return res;
}
}Fruit Into Baskets solution in Python
class Solution:
def totalFruit(self, fruits: List[int]) -> int:
count = defaultdict(int) # Dictionary to store fruit frequencies
l = 0
total = 0
res = 0
for r in range(len(fruits)):
# Add current fruit
count[fruits[r]] += 1
total += 1
# Shrink window if more than 2 fruit types
while len(count) > 2:
f = fruits[l]
count[f] -= 1
total -= 1
if count[f] == 0:
del count[f] # Remove type if count is 0
l += 1
# Update max result
res = max(res, total)
return resFruit Into Baskets solution in JavaScript
/**
* @param {number[]} fruits
* @return {number}
*/
var totalFruit = function(fruits) {
let count = new Map(); // Map to store fruit type counts
let l = 0, total = 0, res = 0;
for (let r = 0; r < fruits.length; r++) {
count.set(fruits[r], (count.get(fruits[r]) || 0) + 1); // Add current fruit
total++;
// Shrink window if more than 2 types
while (count.size > 2) {
let f = fruits[l];
count.set(f, count.get(f) - 1);
total--;
if (count.get(f) === 0) {
count.delete(f); // Remove type if count is 0
}
l++;
}
res = Math.max(res, total); // Update max result
}
return res;
};Fruit Into Baskets Complexity Analysis
Time Complexity: O(n)
Let n be the number of fruits (i.e., the length of the fruits[] array).
1. Outer Loop: r from 0 to n-1
- This loop runs exactly n times, once for each fruit in the array.
- Every iteration adds one fruit to the window.
- So this part takes O(n) time.
2. Inner Loop (while count.size() > 2)
- This loop removes fruits from the left of the window.
- The key observation is:
- Each fruit is added once and removed once.
- So the left pointer l moves at most n times across the array.
Even though there’s a while-loop inside the for-loop, the total number of operations across all iterations is at most 2n:
- Each fruit is processed at most twice: once when added (r++), once when removed (l++).
So, even in the worst case, the combined work done by both pointers is linear.
3. Map Operations
- Each insert, update, or erase operation in the map/dictionary is O(1) on average (amortized for hash-based maps).
- The number of keys in the map never exceeds 3 at any time (we immediately delete keys with count 0), so even in worst-case scenarios, map operations remain constant time.
Final Time Complexity: O(n)
- The right pointer (r) iterates over n elements.
- The left pointer (l) moves forward at most n times.
- Map operations are O(1) on average per operation.
- Hence, overall time complexity is O(n).
Space Complexity: O(1)
Let’s assume the input array fruits has length n.
Auxiliary Space Complexity
Auxiliary space includes only the extra memory used by the algorithm (not including the input or output).
Data Structures Used:
- A map/dictionary (count) to store the count of each fruit type in the current window.
- At any time, it holds at most 3 fruit types (only temporarily — we immediately delete the third when invalid).
- So the size of the map is bounded by a constant (≤ 3).
Other Variables:
- Pointers l, r, integers like total, res → all are scalar values → O(1) space.
Auxiliary Space = O(1) (constant)
Total Space Complexity
This includes:
- Input array: fruits → size n → O(n)
- Output: a single integer → O(1)
- Auxiliary space from above → O(1)
Total Space = O(n)
Similar Problems
Now we have successfully tackled this problem, let's try these similar problems:-
You are given two arrays of integers, fruits and baskets, each of length n, where fruits[i] represents the quantity of the ith type of fruit, and baskets[j] represents the capacity of the jth basket.
From left to right, place the fruits according to these rules:
- Each fruit type must be placed in the leftmost available basket with a capacity greater than or equal to the quantity of that fruit type.
- Each basket can hold only one type of fruit.
- If a fruit type cannot be placed in any basket, it remains unplaced.
Return the number of fruit types that remain unplaced after all possible allocations are made.
You are given an array nums consisting of positive integers.
We call a subarray of nums nice if the bitwise AND of every pair of elements that are in different positions in the subarray is equal to 0.
Return the length of the longest nice subarray.
A subarray is a contiguous part of an array.
Note that subarrays of length 1 are always considered nice.