Sliding Window - Fruits Into Basket

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 i^th 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].

Constraints:

1 <= fruits.length <= 10⁵
0 <= fruits[i] < fruits.length

Solution 1 - Using sliding window technique and a HashMap to keep how many distinguished fruit types are collected

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.

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Implementation steps:

Complexity Analysis: