313. Fruit Into Baskets

Pick a starting tree, then keep walking right while you've collected at most two distinct fruit types. Take the maximum length over every starting point.

Approach

1. For each i from 0 to n - 1:
   • Track the set of fruit types collected so far.
   • Walk j from i until adding fruits[j] would push the set's size past 2.
   • Update the answer with j - i.

Complexity

• Time: O(n²) — every start re-scans the suffix.
• Space: O(1) — the set holds at most three values before we stop.

import java.util.*;

class Solution {
    public int totalFruit(int[] fruits) {
        int n = fruits.length;
        int best = 0;
        for (int i = 0; i < n; i++) {
            Set<Integer> seen = new HashSet<>();
            for (int j = i; j < n; j++) {
                seen.add(fruits[j]);
                if (seen.size() > 2) break;
                best = Math.max(best, j - i + 1);
            }
        }
        return best;
    }
}

The brute force re-explores the same suffix from many starts. Instead, slide a window over the array — extend the right edge by adding fruits, and only shrink the left edge when the window has too many distinct types. The window's size at any moment is a valid answer; track the largest.

What the problem really asks

Re-read the problem: "longest contiguous subarray containing at most two distinct values". The basket rules are just flavour text — once you start, you walk right collecting one fruit per tree and you can hold up to two distinct types. So the answer is the maximum window length such that the window contains at most 2 distinct fruit types.

The sliding window

Imagine a window [left, right] over the array, plus a small dictionary count that says how many trees of each fruit type are currently inside the window:

fruits = [3, 3, 3, 1, 2, 1, 1, 2, 3, 3, 4]
                         [left ............. right]
                         {1: 3, 2: 2}   ← only 2 distinct, OK

We grow right one step at a time. Whenever the window collects a third distinct fruit, we shrink from the left until only two types remain.

Steps

1. Initialise count = {}, left = 0, best = 0.
2. For each right from 0 to n - 1:
   • Add fruits[right] to the window: count[fruits[right]] += 1.
   • Shrink while invalid: while the window has more than 2 distinct types,
     • Decrement count[fruits[left]]. If that count reaches 0, remove the key — that fruit type no longer exists in the window.
     • left += 1.
   • Update best = max(best, right - left + 1).
3. Return best.

Walk-through

fruits = [3, 3, 3, 1, 2, 1, 1, 2, 3, 3, 4]. We follow the window step by step.

Answer: 5.

Why each pointer is monotone

right only moves forward (it's the loop variable). left only moves forward (the while loop only ever advances it). So each index is added at most once and removed at most once — that's the linear-time guarantee.

Edge cases

• Single fruit type throughout: the inner while never fires; the answer is n.
• n == 1: loop runs once, best = 1.

Complexity

• Time: O(n) — each index touched at most twice.
• Space: O(1) — the counter holds at most 3 entries (it spikes to 3, then we shrink it back to 2).