You are given an array fruits where each element represents a type of fruit growing on a tree in a row. You have two baskets, and each basket can only hold one type of fruit, but you can have as many fruits of that type as you want. Starting from any tree, you must pick exactly one fruit from every tree moving to the right (i.e., you cannot skip trees), and you must stop when you pick a fruit that cannot fit in either of your baskets (meaning you now have three different types).
Your task is to find the length of the longest contiguous subarray that contains at most two different types of fruits. In other words, what is the maximum number of fruits you can collect with two baskets, picking from consecutive trees only?
Constraints:
fruits is an integer representing a fruit type.At first glance, this problem looks similar to finding the longest subarray with at most two distinct numbers. A brute-force approach would be to check every possible subarray and count the number of unique fruit types, keeping track of the maximum length that contains at most two types. However, this would be very inefficient for large arrays.
To optimize, we can use the "sliding window" technique, which is ideal for problems involving contiguous subarrays and constraints on the number of unique elements. The key insight is that as soon as our window (subarray) contains more than two types, we can move the start of the window forward until we're back to just two types. This way, we efficiently explore all possible valid subarrays in a single pass.
Using a hash map (or dictionary) to track the count of each fruit type in our current window allows us to quickly check how many types are present and adjust the window as needed.
We'll use the sliding window technique with two pointers (left and right) to represent the current range of trees being considered. We'll also use a hash map to keep track of how many fruits of each type are in the window.
left and right, at the start of the array. Also initialize a hash map to count fruit types, and a variable to track the maximum window length.
right one step at a time. For each fruit, increase its count in the hash map.
left forward and decreasing the count of the fruit at left in the hash map. If a fruit's count drops to zero, remove it from the hash map.
right reaches the end of the array.
This approach ensures each element is processed at most twice (once when right enters, once when left leaves), making it very efficient.
Let's walk through an example with fruits = [1,2,1,2,3,2,2,1].
left = 0, right = 0, window = [1]. Hash map: {1:1}.
right to 1: window = [1,2]. Hash map: {1:1, 2:1}.
right to 2: window = [1,2,1]. Hash map: {1:2, 2:1}.
right to 3: window = [1,2,1,2]. Hash map: {1:2, 2:2}.
right to 4: window = [1,2,1,2,3]. Hash map: {1:2, 2:2, 3:1} (now three types).
left=0 (now {1:1,2:2,3:1}), move left to 1.
left=1 (now {1:1,2:1,3:1}), move left to 2.
left=2 (now {1:0,2:1,3:1}), remove 1, move left to 3. Hash map now {2:1, 3:1}.
right and updating window length.
fruits. Space complexity is O(1), since the hash map stores at most three fruit types (but only two at any time).
from collections import defaultdict
class Solution:
def totalFruit(self, fruits):
count = defaultdict(int)
left = 0
max_len = 0
for right, fruit in enumerate(fruits):
count[fruit] += 1
while len(count) > 2:
count[fruits[left]] -= 1
if count[fruits[left]] == 0:
del count[fruits[left]]
left += 1
max_len = max(max_len, right - left + 1)
return max_len
#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
int totalFruit(vector<int>& fruits) {
unordered_map<int, int> count;
int left = 0, max_len = 0;
for (int right = 0; right < fruits.size(); ++right) {
count[fruits[right]]++;
while (count.size() > 2) {
count[fruits[left]]--;
if (count[fruits[left]] == 0)
count.erase(fruits[left]);
left++;
}
max_len = max(max_len, right - left + 1);
}
return max_len;
}
};
import java.util.*;
class Solution {
public int totalFruit(int[] fruits) {
Map<Integer, Integer> count = new HashMap<>();
int left = 0, maxLen = 0;
for (int right = 0; right < fruits.length; right++) {
count.put(fruits[right], count.getOrDefault(fruits[right], 0) + 1);
while (count.size() > 2) {
count.put(fruits[left], count.get(fruits[left]) - 1);
if (count.get(fruits[left]) == 0) {
count.remove(fruits[left]);
}
left++;
}
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
}
var totalFruit = function(fruits) {
let count = new Map();
let left = 0, maxLen = 0;
for (let right = 0; right < fruits.length; right++) {
count.set(fruits[right], (count.get(fruits[right]) || 0) + 1);
while (count.size > 2) {
count.set(fruits[left], count.get(fruits[left]) - 1);
if (count.get(fruits[left]) === 0) {
count.delete(fruits[left]);
}
left++;
}
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
};
The "Fruit Into Baskets" problem is a classic example of using the sliding window technique to efficiently find the longest contiguous subarray that meets certain constraints—in this case, containing at most two distinct types. By maintaining a hash map of fruit counts and dynamically adjusting the window, we achieve an elegant O(n) solution that is simple, efficient, and easy to understand. The approach not only avoids brute-force inefficiency but also demonstrates the power of hash maps and two-pointer techniques for problems involving subarrays and uniqueness constraints.