LeetCode 3477 - Fruits Into Baskets II

Difficulty: 🟢 Easy
Topics: Array, Binary Search, Segment Tree, Simulation, Ordered Set

Solution

Problem Understanding

This problem asks us to simulate the placement of fruits into baskets following very specific rules. We are given two arrays of equal length, fruits and baskets. Each element in fruits represents the quantity of a fruit type, and each element in baskets represents the capacity of a basket. We need to place each fruit type into the leftmost basket that can hold it. Once a basket is used, it cannot be used again, and if a fruit type cannot fit into any remaining basket, it remains unplaced.

The input constraints indicate that the length of the arrays, n, is up to 100 and each quantity and capacity can be up to 1000. This means that even an O(n²) solution is acceptable. Edge cases include when all fruits fit exactly into baskets, when no fruits fit at all, when multiple fruits have the same quantity, or when multiple baskets have the same capacity. The problem guarantees that the arrays are non-empty and of the same length.

The expected output is the number of fruits that could not be placed according to the rules.

Approaches

The brute-force approach is straightforward. For each fruit, we iterate through the baskets from left to right, checking if the basket has sufficient capacity and is unused. If such a basket is found, we mark it as used and move to the next fruit. If no basket can hold the fruit, we increment the count of unplaced fruits. This approach is simple and correct because it directly simulates the placement rules, but it requires iterating over the baskets for every fruit, resulting in O(n²) time complexity.

The optimal approach improves slightly by maintaining a list of available baskets. Instead of marking used baskets in place, we can remove the basket once it is used. This avoids extra bookkeeping and keeps the implementation clean. Since n is small, the time complexity remains O(n²), but the code is more readable and directly reflects the problem rules. There is no significant asymptotic improvement because we must check the baskets sequentially.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Iterate each fruit over all baskets, mark used baskets
Optimal	O(n²)	O(n)	Maintain list of available baskets, remove basket when used

Algorithm Walkthrough

Initialize a counter unplaced to 0 to track the number of fruit types that cannot be placed.
Create a boolean array used of length n to track which baskets have already been occupied.
Iterate over each fruit in the fruits array:
For the current fruit quantity, iterate over all baskets from left to right.
If a basket is unused and has a capacity greater than or equal to the fruit quantity, place the fruit in this basket by marking it as used and break out of the inner loop.
If no suitable basket is found, increment the unplaced counter.
After all fruits are processed, return the unplaced counter.

Why it works: The algorithm maintains the invariant that a basket, once used, cannot be reused, and the left-to-right iteration ensures that each fruit is placed in the leftmost available basket that can accommodate it. This guarantees correct simulation of the problem rules.

Python Solution

from typing import List

class Solution:
    def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
        n = len(fruits)
        used = [False] * n
        unplaced = 0
        
        for fruit in fruits:
            placed = False
            for i in range(n):
                if not used[i] and baskets[i] >= fruit:
                    used[i] = True
                    placed = True
                    break
            if not placed:
                unplaced += 1
                
        return unplaced

The Python code follows the algorithm closely. The used array ensures that each basket is only occupied once, and the nested loop checks each basket sequentially. The placed flag indicates whether the fruit has found a suitable basket. If not, we increment unplaced.

Go Solution

func numOfUnplacedFruits(fruits []int, baskets []int) int {
    n := len(fruits)
    used := make([]bool, n)
    unplaced := 0

    for _, fruit := range fruits {
        placed := false
        for i := 0; i < n; i++ {
            if !used[i] && baskets[i] >= fruit {
                used[i] = true
                placed = true
                break
            }
        }
        if !placed {
            unplaced++
        }
    }

    return unplaced
}

The Go implementation mirrors the Python solution. The used slice tracks basket usage, and the nested loops simulate the placement. Go requires explicit slice allocation, and boolean initialization defaults to false, which matches the expected initial state.

Worked Examples

Example 1

Input: fruits = [4,2,5], baskets = [3,5,4]

Step	Fruit	Basket Consideration	Action	unplaced
1	4	3	Too small	0
1	4	5	Place	0
2	2	3	Place	0
3	5	4	Too small	0
3	5	(next baskets used)	Cannot place	1

Output: 1

Example 2

Input: fruits = [3,6,1], baskets = [6,4,7]

Step	Fruit	Basket Consideration	Action
1	3	6	Place
2	6	4	Too small
2	6	7	Place
3	1	4	Place

Output: 0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	For each fruit, we may iterate through all baskets to find a suitable one
Space	O(n)	The `used` array tracks the usage of baskets

Since n ≤ 100, O(n²) is acceptable for the input constraints.

Test Cases

# Provided examples
assert Solution().numOfUnplacedFruits([4,2,5], [3,5,4]) == 1  # one fruit cannot be placed
assert Solution().numOfUnplacedFruits([3,6,1], [6,4,7]) == 0  # all fruits placed

# Boundary cases
assert Solution().numOfUnplacedFruits([1], [1]) == 0           # smallest possible input
assert Solution().numOfUnplacedFruits([2], [1]) == 1           # fruit too large for basket

# Multiple fruits same size
assert Solution().numOfUnplacedFruits([2,2,2], [2,2,1]) == 1   # last fruit cannot be placed

# Multiple baskets same size
assert Solution().numOfUnplacedFruits([3,3,3], [3,3,3]) == 0   # all can fit exactly

# No fruit fits
assert Solution().numOfUnplacedFruits([10,20,30], [1,2,3]) == 3

Test	Why
[4,2,5], [3,5,4]	Tests the case where one fruit cannot be placed
[3,6,1], [6,4,7]	Tests the case where all fruits can be placed
[1], [1]	Minimal input
[2], [1]	Fruit cannot fit
[2,2,2], [2,2,1]	Multiple fruits of same size
[3,3,3], [3,3,3]	Multiple baskets of same size
[10,20,30], [1,2,3]	No fruits fit any basket

Edge Cases

One important edge case is when all baskets are smaller than all fruits. This ensures that the code correctly increments unplaced for every fruit. Another edge case occurs when all baskets exactly match fruit quantities; the algorithm must still mark baskets as used and not reuse them. A third edge case is when multiple fruits or baskets have the same value; the algorithm must still place fruits into the leftmost available basket, which tests the left-to-right traversal logic. Each of these cases is correctly handled by the nested iteration and the used array or slice.