# Fruit Into Baskets
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/fruit-into-baskets)
Canonical: https://scaleengineer.com/dsa/problems/fruit-into-baskets
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** Array, Hash Table
**Companies:** [Deutsche Bank](https://scaleengineer.com/companies/deutsche-bank), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs)
---
## Problem
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 <= 105`
* `0 <= fruits[i] < fruits.length`

# Approaches
## Brute Force
The brute-force approach is the most straightforward way to solve the problem. It involves checking every possible contiguous subarray of fruits, simulating the picking process for each, and keeping track of the maximum number of fruits that can be collected according to the rules.
**Time:** O(n^2), where n is the number of trees. The nested loops (one for the start of the subarray and one for the end) lead to a quadratic time complexity. · **Space:** O(1), as the `HashSet` will store at most 3 distinct fruit types before the inner loop breaks.
**Pros:** Simple to understand and implement.; Directly models the logic described in the problem statement.
**Cons:** Highly inefficient due to nested loops, leading to a Time Limit Exceeded error on large inputs.; Redundant calculations as it re-evaluates overlapping subarrays multiple times.
### Explanation
We iterate through all possible starting points `i` from `0` to `n-1`. For each `i`, we start another loop with `j` from `i` to `n-1` to define the end of the current subarray `[i, j]`. We use a `HashSet` to store the types of fruits in the current subarray. As we expand the subarray by incrementing `j`, we add `fruits[j]` to the set. If at any point the size of the set exceeds 2, it means we have encountered a third type of fruit. We cannot pick this fruit, so we stop for this starting point. The length of the valid subarray is the number of fruits we picked before stopping. We keep track of the maximum length found across all starting points.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int totalFruit(int[] fruits) {
        int maxPicked = 0;
        for (int i = 0; i < fruits.length; i++) {
            Set<Integer> basket = new HashSet<>();
            int currentPicked = 0;
            for (int j = i; j < fruits.length; j++) {
                basket.add(fruits[j]);
                if (basket.size() <= 2) {
                    currentPicked++;
                } else {
                    break;
                }
            }
            if (currentPicked > maxPicked) {
                maxPicked = currentPicked;
            }
        }
        return maxPicked;
    }
}
```
### Algorithm
* Initialize a variable `maxPicked` to 0.
* Iterate through each index `i` of the `fruits` array, considering it as a starting point.
  * For each starting point `i`, initialize an empty set `basket` and a counter `currentPicked`.
  * Iterate from index `j = i` to the end of the array.
    * Add `fruits[j]` to the `basket`.
    * If the number of distinct fruits in `basket` is more than 2, break the inner loop.
    * Otherwise, increment `currentPicked`.
  * After the inner loop, update `maxPicked` with the maximum of `maxPicked` and `currentPicked`.
* Return `maxPicked`.

## Sliding Window
This problem can be rephrased as finding the longest subarray with at most two distinct elements. This is a classic problem that can be solved efficiently using a sliding window approach. We maintain a "window" (a subarray) and expand it to the right. When the window becomes invalid (contains more than two fruit types), we shrink it from the left until it's valid again, ensuring we only traverse the array once.
**Time:** O(n), where n is the number of trees. Each element is processed by the `right` pointer once and the `left` pointer at most once, resulting in a linear time complexity. · **Space:** O(1), as the `HashMap` will store at most 3 distinct fruit types at any given time.
**Pros:** Optimal time complexity, making it very efficient for large inputs.; Effectively solves the problem by avoiding the redundant computations of the brute-force method.
**Cons:** Slightly more complex to conceptualize and implement compared to the brute-force approach.
### Explanation
We use two pointers, `left` and `right`, to define the current window `[left, right]`. A `HashMap` is used to store the frequency of each fruit type within this window. We iterate through the `fruits` array with the `right` pointer to expand the window. For each fruit `fruits[right]`, we add it to our window and update its count in the `HashMap`.

After expanding, we check if the window has become invalid, which happens if the number of distinct fruits (`map.size()`) is greater than 2. If it is, we shrink the window from the left by moving the `left` pointer. We decrement the count of `fruits[left]` in the map, and if a fruit's count drops to zero, we remove it entirely from the map. This shrinking process continues until the window is valid again (`map.size() <= 2`).

At each step, after ensuring the window is valid, we calculate its size (`right - left + 1`) and update our `maxPicked` variable if the current window is larger. This single pass through the array ensures that each element is visited by the `left` and `right` pointers at most once.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int totalFruit(int[] fruits) {
        if (fruits == null || fruits.length == 0) {
            return 0;
        }
        int maxPicked = 0;
        int left = 0;
        Map<Integer, Integer> basket = new HashMap<>();
        
        for (int right = 0; right < fruits.length; right++) {
            int currentFruit = fruits[right];
            basket.put(currentFruit, basket.getOrDefault(currentFruit, 0) + 1);
            
            while (basket.size() > 2) {
                int leftFruit = fruits[left];
                basket.put(leftFruit, basket.get(leftFruit) - 1);
                if (basket.get(leftFruit) == 0) {
                    basket.remove(leftFruit);
                }
                left++;
            }
            
            maxPicked = Math.max(maxPicked, right - left + 1);
        }
        
        return maxPicked;
    }
}
```
### Algorithm
* Initialize `left = 0`, `maxPicked = 0`.
* Create a `HashMap` `basket` to store counts of fruits in the window.
* Iterate with a `right` pointer from 0 to `n-1`.
  * Add `fruits[right]` to the `basket` (or increment its count).
  * While the number of distinct fruits in `basket` is greater than 2:
    * Get the fruit at the `left` pointer, `fruitToRemove`.
    * Decrement its count in `basket`.
    * If its count becomes 0, remove it from `basket`.
    * Increment `left`.
  * Update `maxPicked` with the maximum of `maxPicked` and the current window size (`right - left + 1`).
* Return `maxPicked`.

# Solutions
### Java

```java
class Solution {
public
  int totalFruit(int[] fruits) {
    Map<Integer, Integer> cnt = new HashMap<>();
    int j = 0, n = fruits.length;
    for (int x : fruits) {
      cnt.put(x, cnt.getOrDefault(x, 0) + 1);
      if (cnt.size() > 2) {
        int y = fruits[j++];
        cnt.put(y, cnt.get(y) - 1);
        if (cnt.get(y) == 0) {
          cnt.remove(y);
        }
      }
    }
    return n - j;
  }
}

```

### Python

```python
class Solution:
    def totalFruit(self, fruits: List[int]) -> int: cnt = Counter() j = 0 for x in fruits: cnt[x] += 1 if len(cnt) > 2: y = fruits[j] cnt[y] -= 1 if cnt[y] == 0: cnt . pop(y) j += 1 return len(fruits) - j

```

### CPP

```cpp
class Solution {
public:
  int totalFruit(vector<int> &fruits) {
    unordered_map<int, int> cnt;
    int j = 0, n = fruits.size();
    for (int &x : fruits) {
      ++cnt[x];
      if (cnt.size() > 2) {
        int y = fruits[j++];
        if (--cnt[y] == 0)
          cnt.erase(y);
      }
    }
    return n - j;
  }
};

```