Fruits Into Baskets II

easy array simulation binary search

Problem

You are given two equal-length arrays fruits and baskets. Going left to right, each fruit type must go into the leftmost still-free basket whose capacity is ≥ that fruit's quantity. Each basket holds only one fruit type; 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 fits no free basket (basket[2]=4 too small). One unplaced → 1.

fruits (comma-separated)

baskets (comma-separated)

def numOfUnplacedFruits(fruits, baskets):
    n = len(fruits)
    used = [False] * n          # which baskets are taken
    unplaced = 0
    for q in fruits:            # each fruit type, left to right
        placed = False
        for j in range(n):      # scan for leftmost free fit
            if not used[j] and baskets[j] >= q:
                used[j] = True  # claim this basket
                placed = True
                break
        if not placed:
            unplaced += 1       # no basket could hold it
    return unplaced

function numOfUnplacedFruits(fruits, baskets) {
  const n = fruits.length;
  const used = new Array(n).fill(false); // taken baskets
  let unplaced = 0;
  for (const q of fruits) {              // each fruit, left to right
    let placed = false;
    for (let j = 0; j < n; j++) {        // leftmost free fit
      if (!used[j] && baskets[j] >= q) {
        used[j] = true;                  // claim this basket
        placed = true;
        break;
      }
    }
    if (!placed) unplaced++;             // nothing could hold it
  }
  return unplaced;
}

int numOfUnplacedFruits(int[] fruits, int[] baskets) {
    int n = fruits.length;
    boolean[] used = new boolean[n];     // taken baskets
    int unplaced = 0;
    for (int q : fruits) {               // each fruit, left to right
        boolean placed = false;
        for (int j = 0; j < n; j++) {    // leftmost free fit
            if (!used[j] && baskets[j] >= q) {
                used[j] = true;          // claim this basket
                placed = true;
                break;
            }
        }
        if (!placed) unplaced++;         // nothing could hold it
    }
    return unplaced;
}

int numOfUnplacedFruits(vector<int>& fruits, vector<int>& baskets) {
    int n = fruits.size();
    vector<bool> used(n, false);          // taken baskets
    int unplaced = 0;
    for (int q : fruits) {               // each fruit, left to right
        bool placed = false;
        for (int j = 0; j < n; j++) {    // leftmost free fit
            if (!used[j] && baskets[j] >= q) {
                used[j] = true;          // claim this basket
                placed = true;
                break;
            }
        }
        if (!placed) unplaced++;         // nothing could hold it
    }
    return unplaced;
}

Explanation

With n ≤ 100 this is a clean simulation: do exactly what the rules describe and count the failures.

We keep a boolean array used marking which baskets are already occupied. We then process fruit quantities one at a time, in their given left-to-right order — the order matters because an earlier fruit can claim a basket a later fruit would have wanted.

For each fruit quantity q we scan the baskets from index 0 upward and stop at the first basket that is both free (!used[j]) and big enough (baskets[j] >= q). That is the leftmost available fit; we mark it used and move on.

If the scan finishes without finding any such basket, that fruit type is unplaced, so we bump the unplaced counter. The answer is the total count of fruits that never found a home.

Example: fruits = [4,2,5], baskets = [3,5,4]. The 4 takes basket 1 (capacity 5), the 2 takes basket 0 (capacity 3), and the 5 finds only basket 2 free with capacity 4 — too small — so it stays unplaced. One unplaced fruit gives the answer 1.

A faster O(n log n) approach uses a segment tree or ordered structure to binary-search for a free large-enough basket, but for these constraints the direct double loop is simplest and plenty fast at O(n²).

Time: O(n²) Space: O(n)