Leetcode 904. Fruit Into Baskets

Problem Explanation:

We are given an array of numbers, where each number represents the type of a fruit from a tree in a row of trees. Starting from any tree, we can add fruits into our baskets repetitively by first adding one piece of fruit from the current tree to our baskets and then moving to the right for the next tree. However, we have only two baskets, and each basket can only carry one type of fruit, though it can carry any amount of that fruit.

The problem asks for the maximum total number of fruits that can be taken following the above procedure of filling the baskets.

Example walk-through:

Consider the given example where the array is [1,2,1].

• We could start at the first tree, hence the first tree fruit (1) goes into the first basket and then the second fruit (2) goes into the second basket. Since the third tree also has fruits of type "1" and we have earlier taken fruits of type "1", it can also be housed in the first basket making the total number of fruits to be 3.

Approach and Solution:

This problem can be approached as a sliding window problem. Here, we maintain a sliding window with no more than two distinct types of fruits(trees). The right pointer is always moving to the right, and while adding the new type of fruit to the basket when three distinct types of fruits are found, we should move the left pointer to the right until total types of fruit become two. We use an unordered map to hold the fruit types and their counts.

Python Solution

The python solution will use an unordered dictionary data structure to hold the fruit types and their counts.

1
2python
3class Solution:
4    def totalFruit(self, fruits):
5        maxFruits = 0
6        fruitCount = {}
7        
8        left = 0
9        for right in range(len(fruits)):
10            fruitCount[fruits[right]] = fruitCount.get(fruits[right], 0) + 1
11            while len(fruitCount) > 2:
12                fruitCount[fruits[left]] -= 1
13                if fruitCount[fruits[left]] == 0:
14                    del fruitCount[fruits[left]]
15                left += 1
16            maxFruits = max(maxFruits, right - left + 1)
17        return maxFruits

In this solution, for each index right, we update our fruit count and while we have more than two types of fruits in our fruit basket, we remove fruits from the left until we have 2 types of fruits left. We then keep updating maxFruits, which is the maximum total number of fruits that can be taken following the constraints.

The same approach can be used for Java, JavaScript, C++, and C# solutions as well.

Remember, please provide the solutions for all these languages or else the review might be incomplete.JavaScript Solution

The JavaScript solution will use a hashmap to hold the fruit types and their counts.

1
2javascript
3var totalFruit = function(fruits) {
4    let maxFruits = 0;
5    let fruitCount = new Map();
6
7    let left = 0;
8    for (let right = 0; right < fruits.length; right++) {
9        fruitCount.set(fruits[right], (fruitCount.get(fruits[right]) || 0) + 1);
10        while (fruitCount.size > 2) {
11            fruitCount.set(fruits[left], fruitCount.get(fruits[left]) - 1);
12            if (fruitCount.get(fruits[left]) === 0){
13                fruitCount.delete(fruits[left]);
14            }
15            left++;
16        }
17        maxFruits = Math.max(maxFruits, right - left + 1);
18    }
19    return maxFruits;
20};

Java Solution

In Java, we use a HashMap to hold the fruit types and their counts.

1
2java
3import java.util.*;
4class Solution {
5    public int totalFruit(int[] fruits) {
6        int maxFruits = 0, left = 0;
7        HashMap<Integer, Integer> fruitCount = new HashMap<>();
8
9        for(int right = 0; right < fruits.length; right++) {
10            fruitCount.put(fruits[right], fruitCount.getOrDefault(fruits[right], 0) + 1);
11            while(fruitCount.size() > 2) {
12                fruitCount.put(fruits[left], fruitCount.get(fruits[left]) - 1);
13                if(fruitCount.get(fruits[left]) == 0){
14                    fruitCount.remove(fruits[left]);
15                }
16                left++;
17            }
18            maxFruits = Math.max(maxFruits, right - left + 1);
19        }
20        return maxFruits;
21    }
22}

In each of the above solutions, the main idea is to maintain a sliding window with at most two different types of fruits. Thus, the maximum length of the window is the maximum number of fruits we can collect. If the number of different fruit types becomes three, we slide the left border of the window to the right until we're left with exactly two types of fruits. This way, we ensure that the window will always satisfy the problem's constraints.