Fruits in Baskets

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;
    }
}

Blog

Prashant Mishra

Join Our Newsletter. No Spam, Only the good stuff.

Related