Fruit Into Baskets

Pick the longest unbroken run of trees that has at most two fruit types, with a sliding window and a count per type.

The idea

Two baskets that each hold one type, and every tree from the start to the end of the run must be picked: so the task is the longest window with at most 2 distinct values. basket counts each type inside the window. Grow on the right; when a third type arrives, drop trees from the left until one type has no trees left in the window.

Code

public static int TotalFruit(int[] fruits) {
    var basket = new Dictionary<int, int>(); // type -> trees of it in the window
    int left = 0, best = 0;
    for (int right = 0; right < fruits.Length; right++) {
        basket[fruits[right]] = basket.GetValueOrDefault(fruits[right]) + 1;
        while (basket.Count > 2) {
            int f = fruits[left++];
            basket[f]--;
            if (basket[f] == 0) basket.Remove(f);
        }
        best = Math.Max(best, right - left + 1);
    }
    return best;
}

Tips

• Remove a type when its count hits 0. Otherwise basket.Count keeps counting types that are no longer in the window.
• This is "longest substring with at most K distinct characters" with K = 2; the same code works for any K.
• Each tree enters once and leaves at most once, so the nested while loop is still O(n) overall.

In the .NET library

GetValueOrDefault returns 0 for a missing key, so adding to the count needs no ContainsKey check.