Fruit Into Baskets

medium array hash map sliding window

Problem

You start at any tree and walk right, picking one fruit per tree. You have two baskets, each can hold any quantity of one fruit type. Return the most fruits you can pick.

Inputfruits = [1,2,1,2,3]

Output4

Equivalent to longest subarray with ≤ 2 distinct values.

fruits (comma-separated)

def totalFruit(fruits):
    cnt = {}
    l = 0
    best = 0
    for r, x in enumerate(fruits):
        cnt[x] = cnt.get(x, 0) + 1
        while len(cnt) > 2:
            cnt[fruits[l]] -= 1
            if cnt[fruits[l]] == 0: del cnt[fruits[l]]
            l += 1
        best = max(best, r - l + 1)
    return best

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

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

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

Explanation

Two baskets each hold one fruit type, and you pick from a contiguous run of trees. So the question is really: what is the longest subarray that contains at most two distinct values? We answer it with a sliding window.

We keep a count map cnt of fruit types in the current window [l, r]. We extend the right edge by including fruits[r]. If that pushes the number of distinct types above 2, we shrink from the left, removing fruits[l] and deleting its key when its count drops to zero, until only two types remain.

After each step the window is valid (≤ 2 types), so we update best with its length r - l + 1. The window never needs to restart from scratch, which is what keeps this efficient.

Example: fruits = [1,2,1,2,3]. The window [1,2,1,2] uses only types 1 and 2 and has length 4. Reaching the 3 would create a third type, so the left edge moves up. The answer is 4.

Every tree is added once and removed at most once, so the scan is linear.

Time: O(n) Space: O(1)