Skip to content

3477. Fruits Into Baskets II

Description

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:

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

Solutions

Solution 1: Simulation

We use a boolean array \(\textit{vis}\) of length \(n\) to record the baskets that have already been used, and a variable \(\textit{ans}\) to record the number of fruits that have not been placed, initially \(\textit{ans} = n\).

Next, we traverse each fruit \(x\). For the current fruit, we traverse all the baskets to find the first unused basket \(i\) with a capacity greater than or equal to \(x\). If found, we decrement \(\textit{ans}\) by \(1\).

After traversing, we return the answer.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of the array \(\textit{fruits}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
        n = len(fruits)
        vis = [False] * n
        ans = n
        for x in fruits:
            for i, y in enumerate(baskets):
                if y >= x and not vis[i]:
                    vis[i] = True
                    ans -= 1
                    break
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public int numOfUnplacedFruits(int[] fruits, int[] baskets) {
        int n = fruits.length;
        boolean[] vis = new boolean[n];
        int ans = n;
        for (int x : fruits) {
            for (int i = 0; i < n; ++i) {
                if (baskets[i] >= x && !vis[i]) {
                    vis[i] = true;
                    --ans;
                    break;
                }
            }
        }
        return ans;
    }
}

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func numOfUnplacedFruits(fruits []int, baskets []int) int {
    n := len(fruits)
    ans := n
    vis := make([]bool, n)
    for _, x := range fruits {
        for i, y := range baskets {
            if y >= x && !vis[i] {
                vis[i] = true
                ans--
                break
            }
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function numOfUnplacedFruits(fruits: number[], baskets: number[]): number {
    const n = fruits.length;
    const vis: boolean[] = Array(n).fill(false);
    let ans = n;
    for (const x of fruits) {
        for (let i = 0; i < n; ++i) {
            if (baskets[i] >= x && !vis[i]) {
                vis[i] = true;
                --ans;
                break;
            }
        }
    }
    return ans;
}

Comments