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:
Given the integer array fruits, return the maximum number of fruits you can pick.
Example 1:
Input: fruits = [1,2,1] Output: 3 Explanation: We can pick from all 3 trees.
Example 2:
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].
Example 3:
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 <= 1050 <= fruits[i] < fruits.lengthThe key idea in Fruit Into Baskets is to find the longest contiguous subarray containing at most two distinct fruit types. This naturally leads to the Sliding Window technique. As you traverse the array, maintain a window that represents the current set of trees you are collecting fruits from.
Use a hash table (or map) to track the count of each fruit type within the current window. Expand the window by moving the right pointer, and whenever the number of distinct fruit types exceeds two, shrink the window from the left until the constraint is satisfied again. During this process, keep updating the maximum window size found.
This approach works efficiently because each element enters and leaves the window at most once. As a result, the algorithm runs in O(n) time while using O(1) extra space since the map stores at most two fruit types.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sliding Window with Hash Map | O(n) | O(1) |
take U forward
Time Complexity: O(n), where n is the length of the fruits array, as each element is processed at most twice (once added and once removed).
Space Complexity: O(1), as the hashmap will hold at most three entries at any time, which is constant space.
1def totalFruit(fruits):
2 basket = {}
3 left = 0
4 max_fruits = 0
5 for right, fruit in enumerate(fruits):
6 basket[fruit] = basket.get(fruit, 0) + 1
7 while len(basket) > 2:
8 basket[fruits[left]] -= 1
9 if basket[fruits[left]] == 0:
10 del basket[fruits[left]]
11 left += 1
12 max_fruits = max(max_fruits, right - left + 1)
13 return max_fruitsThis code uses a sliding window approach with a hashmap to keep track of fruit counts. The window expands by incrementing 'right' and shrinks from 'left' when more than two types of fruits are in the window. The 'max_fruits' variable is updated with the size of the largest valid window found.
Time Complexity: O(n), as we ensure each element is considered just a limited number of times.
Space Complexity: O(1), since the additional storage for control variables is constant.
1def totalFruit(fruits):
2 n = len(fruits)
3Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem is considered a classic sliding window interview question and has appeared in interviews at large tech companies. It tests understanding of two-pointer techniques, hash maps, and window management.
A hash map (or dictionary) is commonly used to track the count of fruit types inside the sliding window. It helps quickly determine when more than two distinct fruits are present and when to shrink the window.
The optimal approach uses the sliding window technique with a hash map to track fruit counts. The window expands while there are at most two fruit types and shrinks when the constraint is violated. This ensures linear time processing of the array.
Sliding window works well because the problem asks for the longest contiguous segment with a constraint on distinct elements. By dynamically expanding and shrinking the window, you can efficiently maintain valid subarrays without reprocessing elements.
This Python function uses two pointers to dynamically track potential subarrays with at most two different types of fruits. The dict `basket` tracks the latest positions of the current fruit types, allowing direct jumps in the array and optimizing the process of finding a new valid window.