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.
1using System.Collections.Generic;
2
3public class Solution {
4 public int TotalFruit(int[] fruits) {
5 Dictionary<int, int> basket = new Dictionary<int, int>();
6 int left = 0, maxFruits = 0;
7 for (int right = 0; right < fruits.Length; right++) {
8 if (basket.ContainsKey(fruits[right]))
9 basket[fruits[right]]++;
10 else
11 basket[fruits[right]] = 1;
12
13 while (basket.Count > 2) {
14 basket[fruits[left]]--;
15 if (basket[fruits[left]] == 0) basket.Remove(fruits[left]);
16 left++;
17 }
18 maxFruits = Math.Max(maxFruits, right - left + 1);
19 }
20 return maxFruits;
21 }
22}In this C# solution, a Dictionary is used to store the count of each fruit type in the current window. The method ensures that the window contains no more than two different types by adjusting the left pointer.
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.