Problem Description

You have two arrays of integers: fruits and baskets, both of length n.

• fruits[i] represents the quantity of the ith type of fruit
• baskets[j] represents the capacity of the jth basket

You need to place fruits into baskets following these rules:

1. Process fruits from left to right (in order from index 0 to n-1)
2. For each fruit type, find the leftmost available basket that has capacity greater than or equal to that fruit's quantity
3. Each basket can hold only one type of fruit (once a basket is used, it cannot be used again)
4. If no suitable basket is found for a fruit type, that fruit remains unplaced

The goal is to return the count of fruit types that remain unplaced after attempting to place all fruits.

For example, if fruits = [4, 2, 5] and baskets = [3, 6, 2]:

• Fruit type 0 (quantity 4): Check baskets from left - basket 0 has capacity 3 (too small), basket 1 has capacity 6 (≥ 4), so place in basket 1
• Fruit type 1 (quantity 2): Check baskets from left - basket 0 has capacity 3 (≥ 2), so place in basket 0
• Fruit type 2 (quantity 5): Check baskets from left - basket 2 has capacity 2 (too small), and baskets 0 and 1 are already used, so this fruit remains unplaced
• Result: 1 fruit type remains unplaced

Intuition

The problem asks us to simulate a greedy allocation process where we try to place each fruit type into the first available basket that can accommodate it. This naturally leads to a straightforward simulation approach.

The key insight is that we need to:

1. Keep track of which baskets have already been used (since each basket can only hold one fruit type)
2. For each fruit, scan through all baskets from left to right to find the first suitable one

We can track basket usage with a boolean array vis where vis[i] = True means basket i has been used. Initially, all baskets are unused (False).

For counting unplaced fruits, we can start with the assumption that all n fruits will be unplaced (ans = n), then decrement this count each time we successfully place a fruit. This is simpler than counting failures.

The algorithm naturally follows the problem constraints:

• We process fruits in order (outer loop through fruits)
• For each fruit x, we check baskets from left to right (inner loop through baskets)
• We only use a basket if it's both available (not vis[i]) and has sufficient capacity (y >= x)
• Once we place a fruit, we mark that basket as used (vis[i] = True) and reduce our unplaced count (ans -= 1)
• If no suitable basket is found in the inner loop, the fruit remains unplaced and we move to the next fruit

This greedy approach works because we're required to use the leftmost suitable basket - there's no benefit to "saving" a basket for later use.

Learn more about Segment Tree and Binary Search patterns.

Solution Approach

The solution implements a simulation approach using a greedy algorithm to place fruits into baskets.

Data Structures Used:

• A boolean array vis of size n to track which baskets have been used
• An integer counter ans initialized to n to track unplaced fruits

Algorithm Steps:

1. Initialize tracking variables:

   • Create vis = [False] * n where all baskets start as unused
   • Set ans = n assuming initially all fruits are unplaced

2. Process each fruit in order:

   for x in fruits:

   For each fruit quantity x, we attempt to find a suitable basket.

3. Find the leftmost suitable basket:

   for i, y in enumerate(baskets):
       if y >= x and not vis[i]:

   • Iterate through baskets from left to right
   • Check two conditions:
     • y >= x: basket capacity y must be at least the fruit quantity x
     • not vis[i]: basket i must not have been used yet

4. Place the fruit if a suitable basket is found:

   vis[i] = True
   ans -= 1
   break

   • Mark basket i as used
   • Decrement the unplaced fruit count
   • Use break to stop searching once we've placed the fruit (greedy choice)

5. Return the result: After processing all fruits, ans contains the count of fruits that couldn't be placed in any basket.

Time Complexity: O(n²) where n is the length of the arrays, as we potentially check all baskets for each fruit in the worst case.

Space Complexity: O(n) for the vis array to track basket usage.

Example Walkthrough

Let's trace through a small example: fruits = [3, 5, 2] and baskets = [4, 2, 5]

Initial Setup:

• vis = [False, False, False] (all baskets available)
• ans = 3 (assume all fruits unplaced initially)

Processing Fruit 0 (quantity = 3):

• Check basket 0: capacity 4 ≥ 3 and not used ✓
• Place fruit 0 in basket 0
• Update: vis = [True, False, False], ans = 2

Processing Fruit 1 (quantity = 5):

• Check basket 0: already used (skip)
• Check basket 1: capacity 2 < 5 (too small)
• Check basket 2: capacity 5 ≥ 5 and not used ✓
• Place fruit 1 in basket 2
• Update: vis = [True, False, True], ans = 1

Processing Fruit 2 (quantity = 2):

• Check basket 0: already used (skip)
• Check basket 1: capacity 2 ≥ 2 and not used ✓
• Place fruit 2 in basket 1
• Update: vis = [True, True, True], ans = 0

Result: All fruits were successfully placed, so 0 fruits remain unplaced.

The algorithm correctly simulates the greedy placement strategy, always choosing the leftmost available basket with sufficient capacity for each fruit type.

Solution Implementation

Time and Space Complexity

The time complexity is O(n × m), where n is the length of the array fruits and m is the length of the array baskets. This is because there is a nested loop structure - the outer loop iterates through all fruits (n iterations), and for each fruit, the inner loop potentially iterates through all baskets (up to m iterations in the worst case). Even though the inner loop may break early, in the worst case scenario where no matches are found or all matches occur at the end of the baskets array, we would need to check all baskets for each fruit.

The space complexity is O(m), where m is the length of the array baskets. This is due to the vis array which has a size equal to the number of baskets. The variable ans and loop variables use constant additional space.

Note: The reference answer appears to be incorrect or referring to a different implementation. The given code has vis = [False] * n where n = len(fruits), but the vis array is actually indexed by basket positions (vis[i] where i comes from enumerate(baskets)), which suggests there might be a bug if the number of baskets differs from the number of fruits. If we assume the code should be vis = [False] * len(baskets), then the space complexity would be O(m) where m is the length of baskets.

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

Common Pitfalls

1. Not Breaking After Finding a Suitable Basket

The Pitfall: A common mistake is forgetting to add the break statement after successfully placing a fruit in a basket. Without the break, the loop continues checking remaining baskets and might place the same fruit multiple times.

Incorrect Code:

for fruit_size in fruits:
    for basket_index, basket_capacity in enumerate(baskets):
        if basket_capacity >= fruit_size and not is_used[basket_index]:
            is_used[basket_index] = True
            unplaced_count -= 1
            # Missing break here! Loop continues...

Why It's Wrong:

• The same fruit could be "placed" in multiple baskets
• The unplaced_count would be decremented multiple times for a single fruit
• Multiple baskets would be marked as used for one fruit

The Fix: Always include break after successfully placing a fruit to ensure each fruit is processed exactly once:

for fruit_size in fruits:
    for basket_index, basket_capacity in enumerate(baskets):
        if basket_capacity >= fruit_size and not is_used[basket_index]:
            is_used[basket_index] = True
            unplaced_count -= 1
            break  # Critical: stop looking for more baskets

2. Incorrectly Initializing the Unplaced Count

The Pitfall: Starting with unplaced_count = 0 and trying to increment it when fruits can't be placed, rather than starting with the total and decrementing.

Incorrect Approach:

unplaced_count = 0  # Wrong initialization
for fruit_size in fruits:
    placed = False
    for basket_index, basket_capacity in enumerate(baskets):
        if basket_capacity >= fruit_size and not is_used[basket_index]:
            is_used[basket_index] = True
            placed = True
            break
    if not placed:
        unplaced_count += 1  # Requires extra tracking

Why the Original Approach is Better:

• Starting with unplaced_count = len(fruits) and decrementing is cleaner
• Avoids needing an extra placed flag variable
• More intuitive: we assume all fruits are unplaced initially, then subtract those we successfully place

3. Using the Wrong Basket Selection Strategy

The Pitfall: Trying to optimize by finding the "best fit" basket (smallest basket that can hold the fruit) instead of the leftmost suitable basket.

Incorrect Code:

# Wrong: trying to find the smallest suitable basket
best_basket = -1
min_capacity = float('inf')
for basket_index, basket_capacity in enumerate(baskets):
    if basket_capacity >= fruit_size and not is_used[basket_index]:
        if basket_capacity < min_capacity:
            min_capacity = basket_capacity
            best_basket = basket_index

if best_basket != -1:
    is_used[best_basket] = True
    unplaced_count -= 1

Why It's Wrong: The problem specifically requires using the leftmost available basket, not the best-fit basket. This greedy leftmost approach is part of the problem requirements, not an optimization choice.