In this post we will solve the LeetCode 904. Fruit Into Baskets problem using the Java programming language.
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: o 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. o 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. o 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. Constraints: o 1 <= fruits.length <= 10^5 o 0 <= fruits[i] < fruits.length Related Topics: o Array o Hash Table o Sliding Window
The two approaches that came to mind are using a hashmap, which should not have the best performance but should be acceptable, and the second using a sliding window, which should be faster than the one using a hashmap.
I will be solving the problem using the Java programming language and the VSCode IDE on a Windows computer. Please note that the simplest approach is to use the on-line IDE provided by LeetCode. I will not be using it because I like to keep the test scaffold and the solution together. Because of such an approach, I will have to develop a simple test scaffold that will input the data, generate the input argument(s), call the function of interest, and display the result. Please note that the test scaffold IS NOT PART OF THE SOLUTION!
public int totalFruit(int[] fruits) {
}
The signature for the problem indicates that we are given an int[] array with the fruits and we need to return the maximum number of fruits we can collect following the requirements provided by LeetCode.
I always like to read the problem description from the source before I start working on a problem. Things may be updated on the website.
1,2,1 main <<< fruits: [1, 2, 1] main <<< n: 3 main <<< totalFruit0: 3 <<< fruits[0]: 1 fruits[1]: 2 <<< r: 0 <<< fruits[1]: 2 fruits[2]: 1 <<< fruits[0]: 1 fruits[2]: 1 <<< r: 1 main <<< totalFruit: 3 0,1,2,2 main <<< fruits: [0, 1, 2, 2] main <<< n: 4 main <<< totalFruit0: 3 <<< fruits[0]: 0 fruits[1]: 1 <<< r: 0 <<< fruits[1]: 1 fruits[2]: 2 <<< fruits[0]: 0 fruits[2]: 2 <<< fruitCount: 2 <<< l: 1 <<< r: 1 <<< fruits[2]: 2 fruits[3]: 2 main <<< totalFruit: 3 1,2,3,2,2 main <<< fruits: [1, 2, 3, 2, 2] main <<< n: 5 main <<< totalFruit0: 4 <<< fruits[0]: 1 fruits[1]: 2 <<< r: 0 <<< fruits[1]: 2 fruits[2]: 3 <<< fruits[0]: 1 fruits[2]: 3 <<< fruitCount: 2 <<< l: 1 <<< r: 1 <<< fruits[2]: 3 fruits[3]: 2 <<< fruits[1]: 2 fruits[3]: 2 <<< r: 2 <<< fruits[3]: 2 fruits[4]: 2 main <<< totalFruit: 4 1,2,1,2,1,2,3,3 main <<< fruits: [1, 2, 1, 2, 1, 2, 3, 3] main <<< n: 8 main <<< totalFruit0: 6 <<< fruits[0]: 1 fruits[1]: 2 <<< r: 0 <<< fruits[1]: 2 fruits[2]: 1 <<< fruits[0]: 1 fruits[2]: 1 <<< r: 1 <<< fruits[2]: 1 fruits[3]: 2 <<< fruits[1]: 2 fruits[3]: 2 <<< r: 2 <<< fruits[3]: 2 fruits[4]: 1 <<< fruits[2]: 1 fruits[4]: 1 <<< r: 3 <<< fruits[4]: 1 fruits[5]: 2 <<< fruits[3]: 2 fruits[5]: 2 <<< r: 4 <<< fruits[5]: 2 fruits[6]: 3 <<< fruits[4]: 1 fruits[6]: 3 <<< fruitCount: 6 <<< l: 5 <<< r: 5 <<< fruits[6]: 3 fruits[7]: 3 main <<< totalFruit: 6 1,0,1,4,1,4,1,2,3 main <<< fruits: [1, 0, 1, 4, 1, 4, 1, 2, 3] main <<< n: 9 main <<< totalFruit0: 5 <<< fruits[0]: 1 fruits[1]: 0 <<< r: 0 <<< fruits[1]: 0 fruits[2]: 1 <<< fruits[0]: 1 fruits[2]: 1 <<< r: 1 <<< fruits[2]: 1 fruits[3]: 4 <<< fruits[1]: 0 fruits[3]: 4 <<< fruitCount: 3 <<< l: 2 <<< r: 2 <<< fruits[3]: 4 fruits[4]: 1 <<< fruits[2]: 1 fruits[4]: 1 <<< r: 3 <<< fruits[4]: 1 fruits[5]: 4 <<< fruits[3]: 4 fruits[5]: 4 <<< r: 4 <<< fruits[5]: 4 fruits[6]: 1 <<< fruits[4]: 1 fruits[6]: 1 <<< r: 5 <<< fruits[6]: 1 fruits[7]: 2 <<< fruits[5]: 4 fruits[7]: 2 <<< fruitCount: 5 <<< l: 6 <<< r: 6 <<< fruits[7]: 2 fruits[8]: 3 <<< fruits[6]: 1 fruits[8]: 3 <<< fruitCount: 5 <<< l: 7 <<< r: 7 main <<< totalFruit: 5 0,1,6,6,4,4,6 main <<< fruits: [0, 1, 6, 6, 4, 4, 6] main <<< n: 7 main <<< totalFruit0: 5 <<< fruits[0]: 0 fruits[1]: 1 <<< r: 0 <<< fruits[1]: 1 fruits[2]: 6 <<< fruits[0]: 0 fruits[2]: 6 <<< fruitCount: 2 <<< l: 1 <<< r: 1 <<< fruits[2]: 6 fruits[3]: 6 <<< fruits[3]: 6 fruits[4]: 4 <<< fruits[1]: 1 fruits[4]: 4 <<< fruitCount: 3 <<< l: 2 <<< r: 3 <<< fruits[4]: 4 fruits[5]: 4 <<< fruits[5]: 4 fruits[6]: 6 <<< fruits[3]: 6 fruits[6]: 6 <<< r: 5 main <<< totalFruit: 5
The test cases are separated by two blank lines.
The first line in each test contains the contents for the `fruits` int[] array. Our test scaffold seems to read the input line, populate the `fruits` array, and display the contents of the array and the number of elements (or fruits) using the `n` variable. This is done to make sure all is well before calling the function of interest with the necessary argument.
It seems we have two implementations of the function of interest. When each call returns the result is displayed. Note that for the second implementation some additional information is being displayed in order to allow us to follow the algorithm and if needed be able to address issues (bugs). Please note that such additional information IS NOT PART OF THE SOLUTION.
/**
* Test scaffold
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read int[] fruits ****
int[] fruits = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< fruits: " + Arrays.toString(fruits));
System.out.println("main <<< n: " + fruits.length);
// **** call function of interest and display result ****
System.out.println("main <<< totalFruit0: " + totalFruit0(fruits));
// **** call function of interest and display result ****
System.out.println("main <<< totalFruit: " + totalFruit(fruits));
}
The test scaffold seems to follow the description of the test cases. It is short and simple. Please note that IT IS NOT PART OF THE SOLUTION.
/**
* Given the integer array fruits,
* return the maximum number of fruits you can pick.
*
* Using HashMap.
*
* Runtime: 29 ms, faster than 65.28% of Java online submissions.
* Memory Usage: 46.7 MB, less than 91.02% of Java online submissions.
*
* 90 / 90 test cases passed.
* Status: Accepted
* Runtime: 29 ms
* Memory Usage: 46.7 MB
*/
static public int totalFruit0(int[] fruits) {
// **** sanity checks ****
int n = fruits.length;
if (n <= 2) return n;
// **** initialization ****
HashMap<Integer, Integer> baskets = new HashMap<>();
int fruitCount = 0;
int maxFruit = 0;
// **** add and remove fruit from baskets - O(n) ****
for (int i = 0 ; i < n; i++) {
// ???? ????
// System.out.println("<<< fruits[" + i + "]: " + fruits[i]);
// **** remove fruit from basket ****
if (baskets.size() == 2 && baskets.containsKey(fruits[i]) == false) {
// **** count of fruit we keep ****
int cnt = 1;
for (int j = i - 2; j >= 0 && fruits[j] == fruits[i - 1]; j--) cnt++;
// ???? ????
// System.out.println("<<< cnt: " + cnt + " of fruit: " + fruits[i - 1]);
// **** update basket and fruit count ****
baskets = new HashMap<>();
baskets.put(fruits[i - 1], cnt);
fruitCount = cnt;
}
// **** add current fruit to basket ****
Integer count = baskets.putIfAbsent(fruits[i], 1);
if (count != null) baskets.put(fruits[i], ++count);
// **** update fruit count ****
fruitCount++;
// **** update max fruit (if needed) ****
maxFruit = Math.max(maxFruit, fruitCount);
}
// **** return max fruit ****
return maxFruit;
}
In this first implementation of the function of interest we will use a hashmap.
We start by performing some sanity checks.
The initialization section declares the hashmap and two additional variables. The `fruitCount` will be used to keep track of the transient count of fruits in our two baskets, and the `maxFruit` will help us track the maximum amounts as we traverse the `fruits` int[] array.
It seems we need to address two conditions. The first condition is encountered when the current fruit is different from the previous one. The second is to count the next piece of fruit which is the same as the previous one.
Please note that if you separate both cases with an if-then-else statement, you will repeat the code that counts the current piece of fruit. What we have in our source code is the result of several attempts to get the proper solution and to simplify it as much as possible making sure the resulting version is easy to follow and understand. Such an approach helps in production when a different developer or you, after a few months, have to enhance or address an issue. Of course that will not happen with this code.
Please note that when you encounter a different fruit type, you need to discard the contents of a single basket. Also the number of fruit you keep in the second basket may include more than one piece of fruit.
/**
* Given the integer array fruits,
* return the maximum number of fruits you can pick.
*
* Using Sliding Window.
*
* Runtime: 5 ms, faster than 94.05% of Java online submissions.
* Memory Usage: 77.7 MB, less than 28.80% of Java online submissions.
*
* 90 / 90 test cases passed.
* Status: Accepted
* Runtime: 5 ms
* Memory Usage: 77.7 MB
*/
static public int totalFruit(int[] fruits) {
// **** sanity checks ****
int n = fruits.length;
if (n <= 2) return n;
// **** initialization ****
int fruitCount = 0;
int l = 0;
int r = -1;
// **** traverse fruits ****
for(int i = 1; i < n; i++) {
// ???? ????
// System.out.println("<<< fruits[" + (i - 1) + "]: " + fruits[i - 1] + " fruits[" + i + "]: " + fruits[i]);
// **** ****
if (fruits[i - 1] != fruits[i]) {
// ???? ????
// if (r >= 0)
// System.out.println("<<< fruits[" + r + "]: " + fruits[r] + " fruits[" + i + "]: " + fruits[i]);
// **** update sliding window (if needed) ****
if (r >= 0 && fruits[i] != fruits[r]) {
// **** update fruit count ****
fruitCount = Math.max(fruitCount, i - l);
// ???? ????
// System.out.println("<<< fruitCount: " + fruitCount);
// **** update left index ****
l = r + 1;
// ???? ????
// System.out.println("<<< l: " + l);
}
// **** update right index ****
r = i - 1;
// ???? ????
// System.out.println("<<< r: " + r);
}
}
// **** return max fruit ****
return Math.max(fruitCount, n - l);
}
In this approach we will use a sliding window.
I left the `println` statements to be able to follow this implementation. Please note that when we encounter a new type of fruit we need to update the maximum count, discard some fruit and in this case update the left `l` and right `r` references used to maintain the sliding window.
You can check the performance of the two implementations in the comments section of each function.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named FruitIntoBaskets.
Please note that the code here presented might not be the best possible solution. After solving a problem, you should take a look at the best accepted solutions provided by the different websites (i.e., HackerRank, LeetCode to name a few). The idea is to learn concepts, not to memorize solutions.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.
Thanks for reading, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John