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.
1import java.util.HashMap;
2
3public class Solution {
4 public int totalFruit(int[] fruits) {
5 HashMap<Integer, Integer> basket = new HashMap<>();
6 int left = 0, maxFruits = 0;
7 for (int right = 0; right < fruits.length; right++) {
8 basket.put(fruits[right], basket.getOrDefault(fruits[right], 0) + 1);
9 while (basket.size() > 2) {
10 basket.put(fruits[left], basket.get(fruits[left]) - 1);
11 if (basket.get(fruits[left]) == 0) basket.remove(fruits[left]);
12 left++;
13 }
14 maxFruits = Math.max(maxFruits, right - left + 1);
15 }
16 return maxFruits;
17 }
18}This Java solution uses a HashMap to track the count of each fruit type within the sliding window. When a third fruit type is encountered, the window is shrunk from the left until only two types remain.
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.