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.lengthThis 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.
C++
Java
C#
JavaScript
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.
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.
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.
| Approach | Complexity |
|---|---|
| Sliding Window with HashMap | 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). |
| Two Pointer Technique | Time Complexity: O(n), as we ensure each element is considered just a limited number of times. |
L5. Fruit Into Baskets | 2 Pointers and Sliding Window Playlist • take U forward • 128,628 views views
Watch 9 more video solutions →Practice Fruit Into Baskets with our built-in code editor and test cases.
Practice on FleetCode