Fruit Into Baskets (Longest Subarray With At Most 2 Disti...

Problem

Each tree in a row produces one type of fruit. Starting from any tree, collect fruit into two baskets, where each basket holds only one type. Find the maximum number of fruits collectible (longest subarray with at most 2 distinct values).

Input:  fruits = [1,2,1,2,3]
Output: 4   ([1,2,1,2])

Python Solution

def total_fruit(fruits):
    counts = {}
    left = 0
    best = 0
    for right, fruit in enumerate(fruits):
        counts[fruit] = counts.get(fruit, 0) + 1
        while len(counts) > 2:
            counts[fruits[left]] -= 1
            if counts[fruits[left]] == 0:
                del counts[fruits[left]]
            left += 1
        best = max(best, right - left + 1)
    return best

C++ Solution

int totalFruit(vector<int>& fruits) {
    unordered_map<int, int> counts;
    int left = 0, best = 0;
    for (int right = 0; right < fruits.size(); right++) {
        counts[fruits[right]]++;
        while (counts.size() > 2) {
            counts[fruits[left]]--;
            if (counts[fruits[left]] == 0) counts.erase(fruits[left]);
            left++;
        }
        best = max(best, right - left + 1);
    }
    return best;
}

Java Solution

class Solution {
    public int totalFruit(int[] fruits) {
        Map<Integer, Integer> counts = new HashMap<>();
        int left = 0, best = 0;
        for (int right = 0; right < fruits.length; right++) {
            counts.merge(fruits[right], 1, Integer::sum);
            while (counts.size() > 2) {
                int leftFruit = fruits[left];
                counts.merge(leftFruit, -1, Integer::sum);
                if (counts.get(leftFruit) == 0) counts.remove(leftFruit);
                left++;
            }
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

Complexity

Time: O(n) — the left pointer only moves forward, and each fruit type is added/removed a bounded number of times. Space: O(1) — the map holds at most 3 distinct fruit types at any point (2 plus the one that triggers a shrink).