# Fruit Into Baskets

# 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 `i<sup>th</sup>` 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:**

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

**Example 2:**

```plaintext
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:**

```plaintext
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<sup>5</sup>`
- `0 <= fruits[i] < fruits.length`

# Solution

### Brute force Approach

Start at each index and extend the subarray while it contains **at most two fruit types**. Stop when a third type appears, then try the next starting index. Keep the maximum length.

**Time:** O(n²) in the worst case.

**Extra space:** O(1) — the set holds at most three types before the loop stops.

```java
class Solution {
    public int totalFruit(int[] fruits) {
        
        int maxLength = 0;

        int n = fruits.length;


        for(int i=0; i<n; i++){
            Set<Integer> set = new HashSet<>();
            int length = 0;
            for(int j=i; j<n; j++){
                set.add(fruits[j]);
                if(set.size()>2){
                    break;
                }
                length += 1;
                maxLength = Math.max(maxLength, length);
            }
        }

        return maxLength;
    }
}
```

### Better Approach

Use a sliding window with **at most two fruit types**. A frequency map tracks how many fruits of each type are in the window.

1. Add the fruit at `r`.
2. If a third type appears, move `l` until only two types remain. Remove a type from the map when its count reaches zero.
3. Update the maximum length using `r - l + 1`.

**Time:** O(n) expected — each pointer moves forward at most `n` times.

**Extra space:** O(1) — the map holds at most three types before shrinking.

```java
class Solution {
    public int totalFruit(int[] fruits) {
        
        int maxLength = 0;

        int n = fruits.length;

        Map<Integer, Integer> map = new HashMap<>();

        int l = 0;
        int r = 0;

        while(r<n){
            
            map.put(fruits[r], map.getOrDefault(fruits[r], 0) + 1);

            while(map.size() > 2){

                if(map.containsKey(fruits[l])){
                    int freq = map.get(fruits[l]);
                    if(freq == 1){
                        map.remove(fruits[l]);
                    }
                    else{
                        map.put(fruits[l], map.getOrDefault(fruits[l], 0) - 1);
                    }
                    l+=1;
                }
            }

 
             maxLength = Math.max(maxLength, r-l+1);

            r+=1;
        }

        return maxLength;
    }
}
```

### Optimal Approach

If the window has more than two types, move `l` only once instead of shrinking fully. The window may still be invalid, so update the maximum only when `map.size() <= 2`.

Each step adds one fruit and removes at most one, so the window length never decreases. This keeps searching for a longer valid window.

**Time:** O(n) expected — the same time complexity as the better approach.

**Extra space:** O(n) in the worst case — an invalid window can retain more than two types in the map.

```java
class Solution {
    public int totalFruit(int[] fruits) {
        
        int maxLength = 0;

        int n = fruits.length;

        Map<Integer, Integer> map = new HashMap<>();

        int l = 0;
        int r = 0;

        while(r<n){
            
            map.put(fruits[r], map.getOrDefault(fruits[r], 0) + 1);

            if(map.size() > 2){

                if(map.containsKey(fruits[l])){
                    int freq = map.get(fruits[l]);
                    if(freq == 1){
                        map.remove(fruits[l]);
                    }
                    else{
                        map.put(fruits[l], map.getOrDefault(fruits[l], 0) - 1);
                    }
                    l+=1;
                }
            }

            if(map.size() <= 2)
                maxLength = Math.max(maxLength, r-l+1);

            r+=1;
        }

        return maxLength;
    }
}
```