Fruit Into Baskets

Problem Statement: You are visiting a farm that has a single row of fruit trees arranged from left to right. The trees are represented by an integer array fruits where fruits[i] is the type of fruit the ith tree produces.

You want to collect as much fruit as possible. However, the owner has some strict rules that you must follow:

• You only have two baskets, and each basket can only hold a single type of fruit. There is no limit on the amount of fruit each basket can hold.
• Starting from any tree of your choice, you must pick exactly one fruit from every tree (including the start tree) while moving to the right. The picked fruits must fit in one of your baskets.
• Once you reach a tree with fruit that cannot fit in your baskets, you must stop.

Given the integer array fruits, return the maximum number of fruits you can pick.

Input: fruits = [1,2,1]
Output: 3
Explanation: We can pick from all 3 trees.

Input: fruits = [0,1,2,2]
Output: 3
Explanation: We can pick from trees [1,2,2].
If we had started at the first tree, we would only pick from trees [0,1].

Input: fruits = [1,2,3,2,2]
Output: 4
Explanation: We can pick from trees [2,3,2,2].
If we had started at the first tree, we would only pick from trees [1,2].

                     ** Understanding The Problem **

// Problem Statement: We are given an array of fruits in which multiple types of fruits are present and we also have 
// only 2 basket and we need to find out the fruits in the basket( same type of fruits in one basket ). so it means
// we have to store only 2 kinds of fruits bcz only 2 baskets are given. So we have to return the max fruits we can
//  return

// Example : {0,1,2,2} , is an array of fruits of 3 types 0 , 1 and 2 but we have only 2 baskets , so we have to
// fill basket with such kinds of fruits so that we gets max fruits. if we consider 0 and 1 (as they are 2 kinds of fruits)
// we get only 2 fruits in the end but if we consider 1 and 2( they are also only 2 kinds of fruits) we store ,1 one(frequency is one) kind
// of fruits and 2 two(frequency is two) kinds of fruits which gives a total of 3 fruits which is max hence we choose this subarray
// i.e from {1,2,2}. And remember we have to choose a subarray.

So, now we understood the problem, let's code this solution.

Method1: Extreme Brute Force

Algorithm

1. Initialize max_picked = 0 to track the maximum number of fruits we can collect.
2. Iterate over the left index left of subarrays.
3. For every subarray starts at the index left, iterate over every index right to fix the end of the subarray.
4. For each subarray (left, right), count the types of fruits it contains.

• If there are no more than 2 types, this subarray is valid, we take its length to update max_picked.
• Otherwise, if the current subarray is invalid, we move on to the next subarray.

5. Once we finish the iteration, return max_picked as the maximum number of fruits, we can collect.

public class BruteForce {
    public static void main(String[] args) {
        int[] fruits = { 0, 1, 2, 2 };
        System.out.println(basket(fruits));
    }

    private static int basket(int[] fruits) {
        // max number of fruits we picked
        int maxPicked = 0;
        // iterate over all subarray (left, right)
        for(int left = 0;left<fruits.length;left++){
            for(int right=0;right<fruits.length;right++){
                // using set for counting the type of fruits
                Set<Integer> basket = new HashSet<>();
                //iterate over the current subarray
                for(int currentIndex = left ; currentIndex<=right;currentIndex++){
                    basket.add(fruits[currentIndex]);
                }
                // If the number of types of fruits in this subarray (types of fruits)
                // is no larger than 2, this is a valid subarray, update 'maxPicked'.
                if(basket.size()>2){
                    maxPicked = Math.max(maxPicked, right-left+1);
                }
            }
        }
        return maxPicked;
    }
}

// Time complexity is O(n3) and Space  complexity is O(n)

Method2: Using HashMap (Optimal Approach)

Algorithm

1. Start with an empty window with left and right as it's left and right index.
2. We iterate over right and add fruits[right] to this window.

• If the number is no larger than 2, meaning that we collect no more than 2 types of fruits, this subarray is valid.
• Otherwise, it is not the right time to expand the window and we must keep its size. Since we have added one fruit from the right side, we should remove one fruit from the left side of the window, and increment left by 1.

3. Once we are done iterating, the difference between left and right stands for the longest valid subarray we encountered, i.e. the maximum number of fruits we can collect.

public class UsingMap {
    public static void main(String[] args) {
        int[] fruits = {0,1,2,2};
        System.out.println(basket(fruits));
    }

    private static int basket(int[] fruits) {
        int count = 0;
        Map<Integer,Integer> map = new HashMap<>();
        // i is front pointer of sliding window
        // j is rear pointer of sliding window
        int i = 0 , j =0;
        for(i=0;i<fruits.length;i++){
            // this line means if the i value of fruits is not present in map then put it and it's freq is 0
            // but if the i value is already present then increment it's freq by 1.
            map.put(fruits[i], map.getOrDefault(fruits[i], 0)+1);
            if(map.size()>2){
                // in case if the size of map becomes greater than 2 then in that case , take item from starting
                // of fruits array and decrement it's freq by 1
                map.put(fruits[j], map.get(fruits[j])-1);
                // then remove the starting element from fruit array inorder to maintain the size 
                if (map.get(fruits[j]) == 0) {
                    map.remove(fruits[j]);
                }
                // then increment the j
                j++;
            }
            // this is for getting the size of our window which is our answer
            count = Math.max(count, i-j+1);
        }
        return count;

    }
}

//Time complexity is O(n) and space complexity is also O(n)

If anyone can solve this problem, with more efficacy in terms of space complexity please feel free to comment on the solution.

Thank You❤️

Leetcode problem: https://leetcode.com/problems/fruit-into-baskets/