Fruits Into Baskets III

medium segment tree binary search array

Problem

You have arrays fruits and baskets, each of length n. fruits[i] is the quantity of fruit type i; baskets[j] is the capacity of basket j.

Going left to right, each fruit type must be placed in the leftmost still-empty basket whose capacity is ≥ the fruit's quantity. Each basket holds only one type, and a fruit that fits nowhere stays unplaced. Return how many fruit types remain unplaced.

Inputfruits = [4,2,5], baskets = [3,5,4]

Output1

4 → basket[1]=5, 2 → basket[0]=3, 5 has no basket left (only basket[2]=4 < 5). One unplaced.

fruits (comma-separated)

baskets (comma-separated)

def numOfUnplacedFruits(fruits, baskets):
    n = len(baskets)
    size = 1
    while size < n:
        size *= 2
    tree = [0] * (2 * size)        # max-capacity segment tree
    for i in range(n):
        tree[size + i] = baskets[i]
    for i in range(size - 1, 0, -1):
        tree[i] = max(tree[2 * i], tree[2 * i + 1])

    def place(fruit):
        if tree[1] < fruit:        # no basket can hold it
            return False
        node = 1                   # descend to leftmost fitting leaf
        while node < size:
            if tree[2 * node] >= fruit:
                node = 2 * node
            else:
                node = 2 * node + 1
        tree[node] = -1            # consume that basket
        node //= 2
        while node >= 1:           # refresh ancestors
            tree[node] = max(tree[2 * node], tree[2 * node + 1])
            node //= 2
        return True

    unplaced = 0
    for f in fruits:
        if not place(f):
            unplaced += 1
    return unplaced

function numOfUnplacedFruits(fruits, baskets) {
  const n = baskets.length;
  let size = 1;
  while (size < n) size *= 2;
  const tree = new Array(2 * size).fill(0); // max-capacity segment tree
  for (let i = 0; i < n; i++) tree[size + i] = baskets[i];
  for (let i = size - 1; i >= 1; i--)
    tree[i] = Math.max(tree[2 * i], tree[2 * i + 1]);

  function place(fruit) {
    if (tree[1] < fruit) return false;    // no basket fits
    let node = 1;                         // descend to leftmost fit
    while (node < size) {
      if (tree[2 * node] >= fruit) node = 2 * node;
      else node = 2 * node + 1;
    }
    tree[node] = -1;                      // consume that basket
    for (node = node >> 1; node >= 1; node >>= 1)
      tree[node] = Math.max(tree[2 * node], tree[2 * node + 1]);
    return true;
  }

  let unplaced = 0;
  for (const f of fruits)
    if (!place(f)) unplaced++;
  return unplaced;
}

int numOfUnplacedFruits(int[] fruits, int[] baskets) {
    int n = baskets.length, size = 1;
    while (size < n) size *= 2;
    int[] tree = new int[2 * size];          // max-capacity segment tree
    for (int i = 0; i < n; i++) tree[size + i] = baskets[i];
    for (int i = size - 1; i >= 1; i--)
        tree[i] = Math.max(tree[2 * i], tree[2 * i + 1]);

    int unplaced = 0;
    for (int f : fruits) {
        if (tree[1] < f) { unplaced++; continue; } // no basket fits
        int node = 1;                        // descend to leftmost fit
        while (node < size)
            node = tree[2 * node] >= f ? 2 * node : 2 * node + 1;
        tree[node] = -1;                     // consume that basket
        for (node >>= 1; node >= 1; node >>= 1)
            tree[node] = Math.max(tree[2 * node], tree[2 * node + 1]);
    }
    return unplaced;
}

int numOfUnplacedFruits(vector<int>& fruits, vector<int>& baskets) {
    int n = baskets.size(), size = 1;
    while (size < n) size *= 2;
    vector<int> tree(2 * size, 0);            // max-capacity segment tree
    for (int i = 0; i < n; i++) tree[size + i] = baskets[i];
    for (int i = size - 1; i >= 1; i--)
        tree[i] = max(tree[2 * i], tree[2 * i + 1]);

    int unplaced = 0;
    for (int f : fruits) {
        if (tree[1] < f) { unplaced++; continue; } // no basket fits
        int node = 1;                        // descend to leftmost fit
        while (node < size)
            node = tree[2 * node] >= f ? 2 * node : 2 * node + 1;
        tree[node] = -1;                     // consume that basket
        for (node >>= 1; node >= 1; node >>= 1)
            tree[node] = max(tree[2 * node], tree[2 * node + 1]);
    }
    return unplaced;
}

Explanation

The naive rule — for each fruit scan the baskets left to right for the first empty one that fits — is O(n²). With up to 10⁵ fruits and baskets that is too slow, so we accelerate the search with a segment tree over basket capacities.

Build a tree where every node stores the maximum remaining capacity in its range. The leaves are the baskets in their original left-to-right order; each internal node is the max of its two children. The root therefore knows the largest capacity left anywhere.

To place a fruit of size f: first check the root. If the global max is below f, no basket can ever hold it, so it is unplaced. Otherwise we walk down from the root, always stepping into the left child when it still contains some basket with capacity ≥ f, and into the right child only when the left cannot help. That guarantees we land on the leftmost qualifying basket.

Once we reach that leaf we consume the basket by setting its value to −1 (an impossible capacity) and bubble the new max up through its ancestors, so it is never reused. Each placement is one root-to-leaf descent plus one leaf-to-root update — O(log n).

Example fruits = [4,2,5], baskets = [3,5,4]: 4 lands in basket 1 (capacity 5), 2 lands in basket 0 (capacity 3), and 5 finds only basket 2 (capacity 4) left, which is too small — so 5 is unplaced and the answer is 1.

Time: O(n log n) Space: O(n)