Sponsored
Sponsored
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)
3 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.