Welcome to Subscribe On Youtube

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}$.

• Java
• C++
• Python
• Go
• TypeScript

• 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;
      }
  }
  

• 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;
      }
  };
  

• 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
  
  

• 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
  }
  
  

• 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;
  }
  
  

All Problems

All Solutions