Brute force approach:
//brute force approach: leading to TLE
class Solution {
public int totalFruit(int[] fruits) {
Set<Integer> set = new HashSet<>();
int n = fruits.length;
int max = 0;
for(int i =0;i<n;i++){
int leftMost = fruits[i];
int count = 0;
for(int j =i;j<n;j++){
if(set.size()<=1){
set.add(fruits[j]);
count++;
}
else if(set.size() ==2 && set.contains(fruits[j])) count++;
else break;
}
max = Integer.max(max,count);
set.remove(leftMost);
}
return max;
}
}
A better approach using two pointers and sliding window
We can think of this problem as max subarray/substring with <condition>, here the condition is we can choose at most 2 different fruit types in
O(2n), note we are not taking logn time complexity of the map (because the map size is very small i.e 2 hence the search and insert time will be constant or close to constant
for worst case scenario think of an input as 3,3,3,3,3,3,1,2..the left will move till 1 which is o(n) hence outer while will run for O(n) and O(n) which is O(2n)
class Solution {
public int totalFruit(int[] fruits) {
HashMap<Integer,Integer> map = new HashMap<>();
int right =0;
int left =0;
int max =0;
int count =0;
int n = fruits.length;
while(right<n){
map.put(fruits[right],map.getOrDefault(fruits[right],0)+1);
while(map.size()>2){
int fruit = fruits[left];
int freq = map.get(fruit);
if(freq == 1) map.remove(fruit);
else map.put(fruit,--freq);
left++;
}
max = Integer.max(max,right-left+1);
right++;
}
return max;
}
}
Optimal approach: O(n)
class Solution {
public int totalFruit(int[] fruits) {
HashMap<Integer,Integer> map = new HashMap<>();
int right =0;
int left =0;
int max =0;
int count =0;
int n = fruits.length;
while(right<n){
map.put(fruits[right],map.getOrDefault(fruits[right],0)+1);
if(map.size()>2){
int fruit = fruits[left];
int freq = map.get(fruit);
if(freq == 1) map.remove(fruit);
else map.put(fruit,--freq);
left++;
}
max = Integer.max(max,right-left+1);
right++;
}
return max;
}
}
Top comments (0)