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.
1#include <unordered_map>
2#include <vector>
3using namespace std;
4
5int totalFruit(vector<int>& fruits) {
6 unordered_map<int, int> basket;
7 int left = 0, max_fruits = 0;
8 for (int right = 0; right < fruits.size(); ++right) {
9 basket[fruits[right]]++;
10 while (basket.size() > 2) {
11 basket[fruits[left]]--;
12 if (basket[fruits[left]] == 0) basket.erase(fruits[left]);
13 left++;
14 }
15 max_fruits = max(max_fruits, right - left + 1);
16 }
17 return max_fruits;
18}Similar to the Python solution, this code uses a sliding window approach with an unordered_map to track fruit counts. The window expands by moving 'right' and shrinks by moving 'left' when more than two types are present in the 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.
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.