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 <= 100
  • 1 <= fruits[i], baskets[i] <= 1000

Examples

Solution

Method 1 – Greedy Leftmost Placement with Used Baskets Tracking

Intuition

We want to place each fruit in the leftmost basket that can hold it, and each basket can be used only once. We can use a simple greedy approach, scanning baskets from left to right for each fruit and marking used baskets.

Approach

  1. Initialize a boolean array to track used baskets.
  2. For each fruit in order:
    • Scan baskets from left to right.
    • If a basket is unused and its capacity is at least the fruit’s quantity, place the fruit and mark the basket as used.
    • If no basket is 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
16
17
18
19

class Solution {
public:
    int unplacedFruits(vector<int>& fruits, vector<int>& baskets) {
        int n = fruits.size(), m = baskets.size(), ans = 0;
        vector<bool> used(m, false);
        for (int i = 0; i < n; ++i) {
            bool placed = false;
            for (int j = 0; j < m; ++j) {
                if (!used[j] && baskets[j] >= fruits[i]) {
                    used[j] = true;
                    placed = true;
                    break;
                }
            }
            if (!placed) ans++;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

type Solution struct{}
func (Solution) unplacedFruits(fruits, baskets []int) int {
    used := make([]bool, len(baskets))
    ans := 0
    for _, f := range fruits {
        placed := false
        for j, b := range baskets {
            if !used[j] && b >= f {
                used[j] = true
                placed = true
                break
            }
        }
        if !placed {
            ans++
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public int unplacedFruits(int[] fruits, int[] baskets) {
        boolean[] used = new boolean[baskets.length];
        int ans = 0;
        for (int f : fruits) {
            boolean placed = false;
            for (int j = 0; j < baskets.length; j++) {
                if (!used[j] && baskets[j] >= f) {
                    used[j] = true;
                    placed = true;
                    break;
                }
            }
            if (!placed) ans++;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    fun unplacedFruits(fruits: IntArray, baskets: IntArray): Int {
        val used = BooleanArray(baskets.size)
        var ans = 0
        for (f in fruits) {
            var placed = false
            for (j in baskets.indices) {
                if (!used[j] && baskets[j] >= f) {
                    used[j] = true
                    placed = true
                    break
                }
            }
            if (!placed) ans++
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def unplacedFruits(self, fruits: list[int], baskets: list[int]) -> int:
        used = [False] * len(baskets)
        ans = 0
        for f in fruits:
            placed = False
            for j, b in enumerate(baskets):
                if not used[j] and b >= f:
                    used[j] = True
                    placed = True
                    break
            if not placed:
                ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
    pub fn unplaced_fruits(fruits: Vec<i32>, baskets: Vec<i32>) -> i32 {
        let mut used = vec![false; baskets.len()];
        let mut ans = 0;
        for &f in &fruits {
            let mut placed = false;
            for (j, &b) in baskets.iter().enumerate() {
                if !used[j] && b >= f {
                    used[j] = true;
                    placed = true;
                    break;
                }
            }
            if !placed {
                ans += 1;
            }
        }
        ans
    }
}
 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 used: boolean[] = Array(baskets.length).fill(false);
    let ans = 0;
    for (const f of fruits) {
      let placed = false;
      for (let j = 0; j < baskets.length; j++) {
        if (!used[j] && baskets[j] >= f) {
          used[j] = true;
          placed = true;
          break;
        }
      }
      if (!placed) ans++;
    }
    return ans;
  }
}

Complexity

  • ⏰ Time complexity: O(n * m), where n is the number of fruits and m is the number of baskets, since each fruit may check all baskets.
  • 🧺 Space complexity: O(m), for the used baskets array.