Fruits Into Basket

In this approach, we are going to apply sliding window technique using two pointers left and right, and using a HashMap to store distinct fruit types and how many of those fruits collected as value, the reason we store fruit type count as value is, when we have to move the sliding window we need to to left pointer until there are only two distinct fruit types are there.

Implementation steps:

• First, create four variables left, right that we will use to adjust the window, a HashMap sum to store fruit type as key and its count as value, and maxFruits to hold the maximum fruits collected result.
• Next, run a while loop until right pointer reaches end of array fruits, and do the following:
  • Take the current fruit type at right pointer and add it to the count map, if the key already exists, increment its count, otherwise add it with value as 1.
  • Then, check if the current window is going out of bounds, that is if the size of count map is greater than 2, since we we have only two baskets, if it is more than 2, then move the sliding window, take the fruit type at left pointer and reduce its count by -1, if the count becomes zero, then remove that element as well, and increment left pointer in a while loop.
  • Next, update the maxFruits with maximum value between current window size and the current maxFruits.
  • At the end of while loop increment right pointer to move to the next element in fruits array.
• Finally, return maxFruits.

import java.util.HashMap;

public class FruitsIntoBasket {

    static int totalFruit(int[] fruits) {
        int left = 0;
        int right =0;
        int maxFruits = 0;
        HashMap<Integer, Integer> count = new HashMap<>();
        while(right < fruits.length) {
            count.merge(fruits[right], 1, Integer::sum);
            // when map size more than 2
            // that means we are going out of bounds as we only have two baskets
            while(count.size() >2) {
                int newVal = count.merge(fruits[left], -1, Integer::sum);
                if(newVal ==0) {
                    count.remove(fruits[left]);
                }
                left++;
            }
            maxFruits = Math.max(maxFruits, right -left+1);
            right++;
        }
        return maxFruits;
    }

    public static void main(String[] args) {
        System.out.println(totalFruit(new int[]{1, 2, 1, 2, 3}));
        System.out.println(totalFruit(new int[]{1, 2, 1}));
        System.out.println(totalFruit(new int[]{0, 1, 2, 2}));
        System.out.println(totalFruit(new int[]{1,2,3,2,2}));

    }
}

Complexity Analysis:

Time complexity: Above code runs in O(n) time, where n is the length of input array fruits.
Space complexity: O(1), though we are using a HashMap, it will contain atmost 2 elements.