Last Updated: 27 Dec, 2020
Fruits and Baskets
Easy
Asked in companies
There are ‘n’ fruit trees that are planted along a road. The trees are numbered from 0 to n-1. The type of fruit each tree bears is represented by an integer from 1 to 'n'.
A Ninja is walking along that road. He has two baskets and wants to put the maximum number of fruits in them. The restriction is that each basket can have only one type of fruit.
Ninja can start with any tree and end at any tree, but once he has started, he cannot skip a tree i.e if he picks fruit from the tree ‘i’, then he has to pick fruit from tree ‘i+1’ before going to the tree ‘i+2’. He will pick one fruit from each tree until he cannot, i.e, he will stop when he has to pick a fruit of the third type because only two different fruits can fill both baskets.
You are given an array ‘arr’. The ‘i’th integer in this array represents the type of fruit tree ‘i’ bears. Return the maximum number of fruits Ninja can put in both baskets after satisfying all the conditions.
For Example:
'arr' = [1, 2, 3]
Here, we have three different types of fruits. We can pick [1, 2] or [2, 3]. We can pick a maximum of two fruits.
Hence, we return 2.
Input format:
The first line contains an integer ‘n’ representing the number of trees.
The second line has ‘n’ elements of array 'arr' that represent the type of fruit in each tree.
Output format :
Output is the maximum number of fruits Ninja can put in both baskets after satisfying all the conditions.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Approaches
We can observe that this problem is the same as finding the maximum subarray that has at most 2 different elements. This problem can be solved as follow-:
- Initialize an integer variable ‘maxFruits’:= 0.
- Run a loop where ‘i’ ranges from 0 to n-1, and for each ‘i’ find the maximum length of a subarray starting from ‘i’ that has at most two distinct elements, this can be done as follows.
- Create a HashMap that will store distinct characters.
- Run a loop where ‘j’ starts from ‘i’ to n-1, and for each ‘j’ insert an element at that index in the HashMap. if the size of HashMap becomes greater than 2 then break the loop, otherwise, update ‘maxFruits’ by a maximum of its current value and j-i+1.
- Return ‘maxFruits’.
This problem follows the Sliding Window pattern. It is quite similar to Longest Subarray with at most two distinct characters (Here fruit types). We can also solve it by maintaining a sliding window as follows.
- Initialize two integer variables‘ start’:= 0 and ‘end’:= 0, representing the start and end of the window.
- Make a Hash Map that will contain unique elements in the current window mapped with their frequency in that window. The size of HashMap will give the count of a distinct element in the current window.
- Initialize an integer variable ‘maxFruits’:= 0.
- Run a while loop till ‘end’ is smaller than ‘n’ and do the following in each iteration -:
- If the element at index ‘end’ is already present in HashMap or the size of HashMap is less than ‘2’, then increment the frequency of this element in the HashMap after inserting (if not already exist) and increment ‘end’ by 1. After that, update ‘maxFruits’ by a maximum of its current value and ‘end’ - ‘start’.
- Otherwise, Decrement the element of the character at index ‘start’ if its frequency becomes 0 then remove it from HashMap. After that increment ‘start’ by 1.
- Return ‘maxFruits’.