Fruits Into Baskets II

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.

Examples

Example 1

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

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

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

C++

class Solution {
public:
    int numOfUnplacedFruits(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;
    }
};

Go

type Solution struct{}
func (Solution) numOfUnplacedFruits(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
}

Java

class Solution {
    public int numOfUnplacedFruits(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;
    }
}

Kotlin

class Solution {
    fun numOfUnplacedFruits(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
    }
}

Python

class Solution:
    def numOfUnplacedFruits(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

Rust

impl Solution {
    pub fn num_of_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
    }
}

TypeScript

class Solution {
  numOfUnplacedFruits(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.