Problem Statement

You are given two arrays fruits and baskets of equal length n. Place fruits into baskets following these rules:

• Each fruit type must be placed in the leftmost available basket with sufficient capacity
• Each basket holds only one type of fruit
• If a fruit cannot be placed, it remains unplaced

Return the number of fruit types that remain unplaced.

Algorithm Walkthrough

Key Ideas

1. Process fruits in order: Iterate through fruits from left to right (index 0 to n-1)
2. Leftmost available rule: For each fruit, scan baskets from left to right to find the first available basket with sufficient capacity
3. Remove used baskets: Instead of tracking which baskets are used, physically remove used baskets from the list
4. Count remaining: The number of remaining baskets equals the number of unplaced fruits

Common Mistake

Sorting the array: A major pitfall is sorting the baskets by capacity to use binary search. This breaks the "leftmost available" requirement since sorting destroys the original positional order that the problem requires.

# WRONG - destroys leftmost requirement
baskets.sort()  
pos = bisect.bisect_left(baskets, fruit)

Full Solution

Python

class Solution:
    def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
        # TC: O(n^2) SC: O(n)
        # For each fruit type (in order from left to right), find the leftmost available basket that can hold it
        # Mark that basket as used once a fruit is placed
        # Count how many fruits couldn't be placed

        # Process each fruit type from left to right
        for fruit_quantity in fruits:
            # Find leftmost available basket with sufficient capacity
            for j, cap in enumerate(baskets):
                if cap >= fruit_quantity:
                    baskets.pop(j)
                    break

        return len(baskets)

Java

class Solution {
    public int numOfUnplacedFruits(int[] fruits, int[] baskets) {
        List<Integer> basketList = new ArrayList<>();
        for (int basket : baskets) {
            basketList.add(basket);
        }

        for (int fruit : fruits) {
            for (int j = 0; j < basketList.size(); j++) {
                if (basketList.get(j) >= fruit) {
                    basketList.remove(j);
                    break;
                }
            }
        }

        return basketList.size();
    }
}

C++

class Solution {
public:
    int numOfUnplacedFruits(vector<int>& fruits, vector<int>& baskets) {
        for (int fruit : fruits) {
            for (auto it = baskets.begin(); it != baskets.end(); ++it) {
                if (*it >= fruit) {
                    baskets.erase(it);
                    break;
                }
            }
        }
        return baskets.size();
    }
};

C

public class Solution {
    public int NumOfUnplacedFruits(int[] fruits, int[] baskets) {
        List<int> basketList = new List<int>(baskets);

        foreach (int fruit in fruits) {
            for (int j = 0; j < basketList.Count; j++) {
                if (basketList[j] >= fruit) {
                    basketList.RemoveAt(j);
                    break;
                }
            }
        }

        return basketList.Count;
    }
}

Golang

func numOfUnplacedFruits(fruits []int, baskets []int) int {
    // Create a copy to avoid modifying the original slice
    basketsCopy := make([]int, len(baskets))
    copy(basketsCopy, baskets)

    for _, fruit := range fruits {
        for j := 0; j < len(basketsCopy); j++ {
            if basketsCopy[j] >= fruit {
                // Remove element at index j
                basketsCopy = append(basketsCopy[:j], basketsCopy[j+1:]...)
                break
            }
        }
    }

    return len(basketsCopy)
}

C

int numOfUnplacedFruits(int* fruits, int fruitsSize, int* baskets, int basketsSize) {
    int remainingBaskets = basketsSize;
    bool used[basketsSize];
    memset(used, false, sizeof(used));

    for (int i = 0; i < fruitsSize; i++) {
        for (int j = 0; j < basketsSize; j++) {
            if (!used[j] && baskets[j] >= fruits[i]) {
                used[j] = true;
                remainingBaskets--;
                break;
            }
        }
    }

    return fruitsSize - (basketsSize - remainingBaskets);
}

Complexity Analysis

Time Complexity: O(n²)

• Outer loop: n fruits
• Inner loop: up to n baskets to scan
• Worst case: each fruit scans all remaining baskets

Space Complexity: O(n)

• We modify the baskets array (or create a copy in some languages)

Is the solution optimal?

Yes, this solution is optimal for this specific problem. Here's why:

Why O(n²) is unavoidable:

1. Order dependency: We must process fruits left-to-right and find the leftmost available basket
2. No preprocessing possible: We cannot sort baskets because their position matters
3. Dynamic state: Basket availability changes as we place fruits, preventing advanced data structures

Why common optimizations don't work:

• Sorting + Binary Search: Violates the "leftmost" requirement
• Heap/Priority Queue: Gives smallest capacity, not leftmost position
• Hash Map: Cannot help with positional requirements

The constraint advantage:

With n ≤ 100, the O(n²) solution performs at most 10,000 operations, which is perfectly acceptable and likely the intended approach by the problem setter.

This greedy simulation approach is both correct and optimal for the given constraints and requirements.