Fruit Into Baskets

Problem

Given an array of fruit types in a row of trees, return the maximum number of fruits you can pick using two baskets, each holding one type, picking consecutive trees.

Constraints

• 1 ≤ fruits.length ≤ 10⁵

Approach — Sliding Window

This is a Sliding Window problem. The idea: keep a moving window over the sequence, expanding and shrinking it while tracking the answer in a single pass. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time.

Solution code

Python

class Solution:
    def totalFruit(self, fruits):
        from collections import defaultdict
        count = defaultdict(int)
        left = best = 0
        for right, f in enumerate(fruits):
            count[f] += 1
            while len(count) > 2:
                count[fruits[left]] -= 1
                if count[fruits[left]] == 0:
                    del count[fruits[left]]
                left += 1
            best = max(best, right - left + 1)
        return best

Java

import java.util.*;
class Solution {
    public int totalFruit(int[] fruits) {
        Map<Integer,Integer> count = new HashMap<>();
        int l = 0, best = 0;
        for (int r = 0; r < fruits.length; r++) {
            count.merge(fruits[r], 1, Integer::sum);
            while (count.size() > 2) {
                int f = fruits[l++];
                if (count.merge(f, -1, Integer::sum) == 0) count.remove(f);
            }
            best = Math.max(best, r - l + 1);
        }
        return best;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.