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.
1function totalFruit(fruits) {
2 const basket = new Map();
3 let left = 0, maxFruits = 0;
4 for (let right = 0; right < fruits.length; right++) {
5 basket.set(fruits[right], (basket.get(fruits[right]) || 0) + 1);
6 while (basket.size > 2) {
7 basket.set(fruits[left], basket.get(fruits[left]) - 1);
8 if (basket.get(fruits[left]) === 0) basket.delete(fruits[left]);
9 left++;
10 }
11 maxFruits = Math.max(maxFruits, right - left + 1);
12 }
13 return maxFruits;
14}This JavaScript solution leverages a Map to maintain counts of fruit types in the window. The main loop adjusts the window until it satisfies the condition of containing up to two types of fruits.
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.