Problem

You are given two arrays of integers, fruits and baskets, each of length n, where fruits[i] represents the quantity of the ith type of fruit, and baskets[j] represents the capacity of the jth basket.

From left to right, place the fruits according to these rules:

  • Each fruit type must be placed in the leftmost available basket with a capacity greater than or equal to the quantity of that fruit type.
  • Each basket can hold only one type of fruit.
  • If a fruit type cannot be placed in any basket, it remains unplaced.

Return the number of fruit types that remain unplaced after all possible allocations are made.

Example 1

1
2
3
4
5
6
7

Input: fruits = [4,2,5], baskets = [3,5,4]
Output: 1
Explanation:
* `fruits[0] = 4` is placed in `baskets[1] = 5`.
* `fruits[1] = 2` is placed in `baskets[0] = 3`.
* `fruits[2] = 5` cannot be placed in `baskets[2] = 4`.
Since one fruit type remains unplaced, we return 1.

Example 2

1
2
3
4
5
6
7

Input: fruits = [3,6,1], baskets = [6,4,7]
Output: 0
Explanation:
* `fruits[0] = 3` is placed in `baskets[0] = 6`.
* `fruits[1] = 6` cannot be placed in `baskets[1] = 4` (insufficient capacity) but can be placed in the next available basket, `baskets[2] = 7`.
* `fruits[2] = 1` is placed in `baskets[1] = 4`.
Since all fruits are successfully placed, we return 0.

Constraints

  • n == fruits.length == baskets.length
  • 1 <= n <= 10^5
  • 1 <= fruits[i], baskets[i] <= 10^9

Examples

Solution

Method 1 – Greedy Leftmost Placement with Ordered Set (Efficient)

Intuition

To efficiently find the leftmost available basket for each fruit, we can use an ordered set or a balanced BST to keep track of available baskets and their indices. This allows us to quickly find the smallest index basket with enough capacity for each fruit, and remove it once used.

Approach

  1. Store all baskets as (capacity, index) pairs in a sorted structure (e.g., TreeSet, SortedList, or use bisect in Python).
  2. For each fruit in order:
    • Use binary search to find the leftmost basket with capacity >= fruit’s quantity.
    • If found, remove that basket from the set.
    • If not found, increment the unplaced count.
  3. Return the total number of unplaced fruits.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#include <set>
class Solution {
public:
    int unplacedFruits(vector<int>& fruits, vector<int>& baskets) {
        set<pair<int, int>> s;
        for (int i = 0; i < baskets.size(); ++i) s.insert({baskets[i], i});
        int ans = 0;
        for (int f : fruits) {
            auto it = s.lower_bound({f, -1});
            if (it == s.end()) ans++;
            else s.erase(it);
        }
        return ans;
    }
};
1

// For Go, sort baskets and use a used array as in the simple greedy, as Go has no built-in ordered set.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

import java.util.TreeSet;
class Solution {
    public int unplacedFruits(int[] fruits, int[] baskets) {
        TreeSet<int[]> set = new TreeSet<>((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
        for (int i = 0; i < baskets.length; i++) set.add(new int[]{baskets[i], i});
        int ans = 0;
        for (int f : fruits) {
            int[] key = {f, -1};
            int[] found = set.ceiling(key);
            if (found == null) ans++;
            else set.remove(found);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

import java.util.TreeSet
class Solution {
    fun unplacedFruits(fruits: IntArray, baskets: IntArray): Int {
        val set = TreeSet(compareBy<Pair<Int, Int>>({ it.first }, { it.second }))
        for (i in baskets.indices) set.add(Pair(baskets[i], i))
        var ans = 0
        for (f in fruits) {
            val found = set.ceiling(Pair(f, -1))
            if (found == null) ans++ else set.remove(found)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

import bisect
class Solution:
    def unplacedFruits(self, fruits: list[int], baskets: list[int]) -> int:
        arr = sorted((b, i) for i, b in enumerate(baskets))
        ans = 0
        for f in fruits:
            idx = bisect.bisect_left(arr, (f, -1))
            if idx == len(arr):
                ans += 1
            else:
                arr.pop(idx)
        return ans
1

// For Rust, use a BTreeSet or Vec with binary search for similar effect.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
  unplacedFruits(fruits: number[], baskets: number[]): number {
    const arr: [number, number][] = baskets.map((b, i) => [b, i]);
    arr.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
    let ans = 0;
    for (const f of fruits) {
      let l = 0, r = arr.length;
      while (l < r) {
        const m = (l + r) >> 1;
        if (arr[m][0] < f) l = m + 1;
        else r = m;
      }
      if (l === arr.length) ans++;
      else arr.splice(l, 1);
    }
    return ans;
  }
}

Complexity

  • ⏰ Time complexity: O(n log n), where n is the number of fruits/baskets, due to sorting and binary search for each fruit.
  • 🧺 Space complexity: O(n), for storing the sorted baskets.