Fruit Into Baskets

Problem#

fruits[i] is the fruit type at tree i. You can carry two baskets; each basket only takes one type. Walk down the row picking one fruit per tree, in order, never skipping. Return the maximum number of fruits.

Examples#

[1,2,1] → 3
[0,1,2,2] → 3
[1,2,3,2,2] → 4

Constraints#

1 <= fruits.length <= 10^5.

Approach#

Longest subarray with at most 2 distinct values. Variable window with a frequency map; shrink while the map has 3 entries.

Solution#

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

func totalFruit(fruits []int) int {
    freq := map[int]int{}
    left, best := 0, 0
    for right := 0; right < len(fruits); right++ {
        freq[fruits[right]]++
        for len(freq) > 2 {
            freq[fruits[left]]--
            if freq[fruits[left]] == 0 {
                delete(freq, fruits[left])
            }
            left++
        }
        if right-left+1 > best {
            best = right - left + 1
        }
    }
    return best
}

from collections import defaultdict
from typing import List

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        freq = defaultdict(int)
        left = 0
        best = 0
        for right in range(len(fruits)):
            freq[fruits[right]] += 1
            while len(freq) > 2:
                freq[fruits[left]] -= 1
                if freq[fruits[left]] == 0:
                    del freq[fruits[left]]
                left += 1
            best = max(best, right - left + 1)
        return best

function totalFruit(fruits) {
    const freq = new Map();
    let left = 0, best = 0;
    for (let right = 0; right < fruits.length; right++) {
        freq.set(fruits[right], (freq.get(fruits[right]) || 0) + 1);
        while (freq.size > 2) {
            freq.set(fruits[left], freq.get(fruits[left]) - 1);
            if (freq.get(fruits[left]) === 0) freq.delete(fruits[left]);
            left++;
        }
        best = Math.max(best, right - left + 1);
    }
    return best;
}

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

function totalFruit(fruits: number[]): number {
    const freq = new Map<number, number>();
    let left = 0, best = 0;
    for (let right = 0; right < fruits.length; right++) {
        freq.set(fruits[right], (freq.get(fruits[right]) ?? 0) + 1);
        while (freq.size > 2) {
            freq.set(fruits[left], freq.get(fruits[left])! - 1);
            if (freq.get(fruits[left]) === 0) freq.delete(fruits[left]);
            left++;
        }
        best = Math.max(best, right - left + 1);
    }
    return best;
}

Editorial#

Generic “at most K distinct” template — replace the > 2 constant with > K. The frequency map’s size is the distinct count, so checking it directly is a one-line invariant. Erasing on zero count keeps the map tight; not erasing also works but inflates map size and confuses the distinct count.

Complexity#

Time: O(n).
Space: O(1) (at most 3 keys live).

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#