Fruit Into Baskets

---

Fruit Into Baskets: 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:

• 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.

Example 1:

Input: fruits = [1,2,1]
Output: 3
Explanation: We can pick from all 3 trees.

---

Example 2:

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].

---

Example 3:

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^5
• 0 <= fruits[i] < fruits.length

---

Try this Problem on your own or check similar problems:

1. Longest Nice Subarray

Solution:

Java

public int totalFruit(int[] fruits) {
    if(fruits.length == 1) return 1;

    int maxFruits = 0, i = 0, j = 0;
    Map<Integer, Integer> map = new HashMap<>();
    while(j < fruits.length){
        map.put(fruits[j], j);

        while(map.size() > 2){
            int minIndex = map.values().stream().min(Integer::compare).get();
            map.remove(fruits[minIndex]);
            i = minIndex + 1;
        }

        maxFruits = Math.max(maxFruits, j - i + 1);
        ++j;
    }
    return maxFruits;
}

JavaScript

/**
 * @param {number[]} fruits
 * @return {number}
 */
var totalFruit = function (fruits) {
  if (fruits.length === 1) return 1;

  let maxFruits = 0;
  let i = 0;
  let j = 0;
  const map = new Map();

  while (j < fruits.length) {
    map.set(fruits[j], j);

    while (map.size > 2) {
      const minIndex = Math.min(...map.values());
      map.delete(fruits[minIndex]);
      i = minIndex + 1;
    }

    maxFruits = Math.max(maxFruits, j - i + 1);
    j++;
  }

  return maxFruits;
};

Python

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        if len(fruits) == 1:
            return 1

        maxFruits = 0
        i = 0
        j = 0
        fruitMap = {}

        while j < len(fruits):
            fruitMap[fruits[j]] = j

            while len(fruitMap) > 2:
                minIndex = min(fruitMap.values())
                del fruitMap[fruits[minIndex]]
                i = minIndex + 1

            maxFruits = max(maxFruits, j - i + 1)
            j += 1

        return maxFruits

C++

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        if (fruits.size() == 1)
            return 1;

        int maxFruits = 0;
        int i = 0;
        int j = 0;
        std::unordered_map<int, int> fruitMap;

        while (j < fruits.size()) {
            fruitMap[fruits[j]] = j;

            while (fruitMap.size() > 2) {
                int minIndex = std::min_element(fruitMap.begin(), fruitMap.end(),
                    [](const auto& p1, const auto& p2) { return p1.second < p2.second; })->second;
                fruitMap.erase(fruits[minIndex]);
                i = minIndex + 1;
            }

            maxFruits = std::max(maxFruits, j - i + 1);
            ++j;
        }

        return maxFruits;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

---

Explanation:

We again use the sliding window approach, so we must define two things:

• how to check if the window is valid
• how to optimize the property of the window (in this case number of fruits or elements in the window)

We keep a map that tracks the latest index of certain fruit, and if we have a map that has more than two elements it means our window is not valid since there can only be two distinct elements in the window. By the problem statement we only have two baskets and in each basket, we can put one fruit type. Each time we find the smallest index one of the fruits has and we remove that fruit and shift our window to point after it i = minIndex + 1. We're also checking if we the current valid window desired property (longest length) is larger than the length we recorded so far. Finally, we return the longest length maxFruits. Note that space complexity is constant since the map can contain at most 3 elements.