3477. Fruits Into Baskets II

EasySegment TreeArrayBinary SearchSimulation

Problem Description

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

The task is to place the fruits into the baskets following these rules:

Each fruit type must be placed in the leftmost available basket that has 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.

You need to return the number of fruit types that remain unplaced after attempting to place all fruits according to the rules.

Intuition

The problem requires simulating the process of placing fruits into baskets. For each fruit type, look for the first basket with enough capacity that hasn't been used yet. Here's the approach:

Initial Setup: Keep track of baskets that are already occupied with a boolean array, vis, of the same length as the baskets. Initialize a counter, ans, with the total number of fruit types, which represents the fruits that haven't been placed yet.
Trial Placement: For each fruit type (starting from the first), iterate through the baskets from the left. Find the first basket that has:
- A capacity that can accommodate the fruit quantity, and
- Has not been used yet (i.e., it's not marked in the vis array).
Update State: If such a basket is found, mark it as used and decrement the counter ans since one more fruit type is successfully placed.
Result: At the end of this process, ans holds the count of the fruit types that couldn't be placed and remained unplaced.

This systematic simulation ensures that we efficiently try to place every fruit type in only suitable baskets, starting from the leftmost, thereby adhering to the rules given in the problem.

Learn more about Segment Tree and Binary Search patterns.

Solution Approach

Solution 1: Simulation

The solution uses a straightforward simulation approach to tackle the problem of placing fruits into baskets:

Variables and Data Structures:
- A boolean array vis is used to keep track of which baskets have already been used. It is initialized to False for all baskets since none are used initially.
- A counter ans is set to the total number of fruit types, n, representing the total number of unplaced fruits initially.
Iterating Over Fruits:
- For each fruit type x in the fruits array:
  - Iterate over all the baskets using their indices and capacities.
  - Check if the basket's capacity y is greater than or equal to the fruit's quantity x and if the basket hasn't been used (not vis[i]).
Placing Fruits:
- As soon as a suitable basket is found that can accommodate the fruit:
  - Mark that basket as used in the vis array (vis[i] = True).
  - Decrease the counter ans by 1 since this fruit type is now placed.
Return the Result:
- After attempting to place all fruit types, ans will reflect the number of fruit types that remain unplaced due to insufficient basket capacity.

This approach efficiently uses a loop within a loop to ensure each fruit type is placed in the first available basket meeting the criteria, aligning with the problem constraints.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's explore the solution approach using a small example. Suppose we have the following arrays:

fruits = [3, 2, 5] representing the quantity of each fruit type.
baskets = [2, 3, 6] representing the capacity of each basket.

We need to place the fruits into the baskets adhering to the specified rules.

Initial Setup:
- We initialize an array vis as [False, False, False] indicating that no baskets are used initially.
- Set the counter ans = 3 because we have three fruit types to start with.
Iterating Over Fruits:
- First Fruit (3):
  - Start with fruits[0] = 3. We'll search for the first basket that can hold this.
  - Check baskets[0] = 2: not enough capacity.
  - Check baskets[1] = 3: enough capacity and unused. Place fruit here.
  - Mark vis[1] = True and decrement ans to 2.
- Second Fruit (2):
  - Next, fruits[1] = 2. Iterate over baskets again.
  - Check baskets[0] = 2: enough capacity and unused. Place fruit here.
  - Mark vis[0] = True and decrement ans to 1.
- Third Fruit (5):
  - For fruits[2] = 5, search the baskets.
  - Check baskets[0] = 2: not enough capacity.
  - Check baskets[1] = 3: not enough capacity.
  - Check baskets[2] = 6: enough capacity and unused. Place fruit here.
  - Mark vis[2] = True and decrement ans to 0.
Result:
- All the fruits have been successfully placed in the baskets.
- The counter ans now reflects 0, indicating there are no unplaced fruit types.

This walkthrough illustrates placing each fruit type in the leftmost available basket with sufficient capacity.

Solution Implementation

1from typing import List
2
3class Solution:
4    def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
5        n = len(fruits)  # Number of fruits
6        visited = [False] * n  # Track which baskets have been used
7        unplaced_count = n  # Initialize unplaced fruit count as total fruit count
8
9        # Iterate over each fruit
10        for fruit in fruits:
11            # Attempt to place the fruit in a suitable basket
12            for index, basket in enumerate(baskets):
13                # Check if the basket can hold the fruit and if the basket is not already used
14                if basket >= fruit and not visited[index]:
15                    visited[index] = True  # Mark this basket as used
16                    unplaced_count -= 1  # Decrease unplaced fruit count
17                    break  # Move to the next fruit once a basket is found
18
19        return unplaced_count  # Return the number of unplaced fruits
20

1class Solution {
2    // Method to calculate the number of unplaced fruits
3    public int numOfUnplacedFruits(int[] fruits, int[] baskets) {
4        int n = fruits.length; // Number of fruits
5        boolean[] visited = new boolean[n]; // Array to track used baskets
6        int unplacedFruits = n; // Initialize all fruits as unplaced
7
8        // Loop through each fruit
9        for (int fruit : fruits) {
10            // Try to place each fruit in an available basket
11            for (int i = 0; i < n; ++i) {
12                // Check if the current basket can hold the fruit
13                // and if it hasn't been used yet
14                if (baskets[i] >= fruit && !visited[i]) {
15                    visited[i] = true; // Mark the basket as used
16                    --unplacedFruits; // Decrease count of unplaced fruits
17                    break; // Move to the next fruit
18                }
19            }
20        }
21        return unplacedFruits; // Return the count of unplaced fruits
22    }
23}
24

1class Solution {
2public:
3    // This function calculates the number of unplaced fruits
4    // given vectors of fruits and baskets.
5    int numOfUnplacedFruits(vector<int>& fruits, vector<int>& baskets) {
6        int n = fruits.size();  // Number of fruits
7        vector<bool> visited(n, false);  // Vector to track if a basket has been used
8        int unplacedFruits = n;  // Initialize the number of unplaced fruits to the total number of fruits
9
10        // Iterate through each fruit
11        for (int fruit : fruits) {
12            // Attempt to place the fruit into a basket
13            for (int i = 0; i < n; ++i) {
14                // Check if the basket can hold the fruit and hasn't been used
15                if (baskets[i] >= fruit && !visited[i]) {
16                    visited[i] = true;  // Mark the basket as used
17                    --unplacedFruits;   // Decrease the count of unplaced fruits
18                    break;  // Move to the next fruit
19                }
20            }
21        }
22        return unplacedFruits;  // Return the total number of unplaced fruits
23    }
24};
25

1// The function numOfUnplacedFruits calculates how many fruits cannot be placed into baskets.
2function numOfUnplacedFruits(fruits: number[], baskets: number[]): number {
3    // Determine the number of fruits (and baskets since they are expected to be the same length).
4    const n: number = fruits.length;
5  
6    // Create a boolean array to track whether each basket has been used.
7    const visited: boolean[] = Array(n).fill(false);
8  
9    // Initialize the answer as the total number of fruits, assuming none are placed initially.
10    let unplacedCount: number = n;
11  
12    // Iterate over each fruit.
13    for (const fruit of fruits) {
14        // Attempt to find a basket for the current fruit.
15        for (let i = 0; i < n; ++i) {
16            // Check if the current basket can accommodate the fruit and hasn't been used yet.
17            if (baskets[i] >= fruit && !visited[i]) {
18                // Mark the basket as used.
19                visited[i] = true;
20                // Decrement the count of unplaced fruits since this fruit can be placed.
21                --unplacedCount;
22                // Break after placing the fruit in a suitable basket.
23                break;
24            }
25        }
26    }
27  
28    // Return the total number of fruits that couldn't be placed in any basket.
29    return unplacedCount;
30}
31

Time and Space Complexity

The time complexity of the code is O(n * m), where n is the length of the fruits array and m is the length of the baskets array. The space complexity is O(m), resulting from the use of the vis list to keep track of used baskets.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which type of traversal does breadth first search do?

Pre-order traversal

Post-order traversal

In-order traversal

Level-order traversal

I don't know