LeetCode Problem 3479

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Segment Tree, Ordered Set

Solution

LeetCode 3479: Fruits Into Baskets III

Problem Understanding

This problem gives us two arrays of equal length:

• fruits[i] represents the quantity of the i-th fruit type.
• baskets[j] represents the capacity of the j-th basket.

We process the fruit types from left to right. For each fruit quantity, we must place it into the leftmost available basket whose capacity is at least as large as the fruit quantity.

A basket can only be used once. After a basket is assigned to a fruit type, it becomes unavailable for all future fruit types.

If no available basket has sufficient capacity, that fruit type remains unplaced.

The goal is to return the total number of fruit types that remain unplaced after processing all fruits.

The key detail is the phrase "leftmost available basket". We are not simply looking for any basket with enough capacity. Among all currently unused baskets that can hold the fruit, we must choose the one with the smallest index.

What the Constraints Tell Us

The array length can be as large as 100,000.

A straightforward simulation would, for every fruit, scan all baskets from left to right until finding a valid unused basket. In the worst case, this requires:

• n fruits
• n basket checks per fruit

This leads to O(n²) time complexity, which would be far too slow for n = 100,000.

Therefore, we need a data structure that can efficiently:

1. Determine whether any available basket can hold a given fruit.
2. Find the leftmost available basket satisfying the capacity requirement.
3. Mark a basket as used.

These requirements naturally suggest a segment tree.

Important Edge Cases

One important edge case occurs when every fruit is larger than every basket. In that situation, none of the fruits can be placed and the answer equals n.

Another important case occurs when multiple baskets can hold a fruit. The problem requires selecting the leftmost available one, not the smallest capacity one. Any solution that greedily chooses baskets based on capacity alone would be incorrect.

A third edge case occurs when a basket that could hold a future fruit gets consumed by an earlier fruit because it is the leftmost valid basket. The placement order is fixed by the problem statement, so we cannot reorder fruits or baskets.

The problem guarantees:

• Both arrays have the same length.
• All values are positive.
• There are no empty arrays.

These guarantees simplify implementation because we never need to handle invalid input.

Approaches

Brute Force

The most direct solution is to simulate the process exactly as described.

For each fruit:

1. Scan baskets from left to right.
2. Skip already-used baskets.
3. Find the first basket whose capacity is at least the fruit quantity.
4. Mark it as used.
5. If no such basket exists, increment the answer.

This approach is obviously correct because it follows the problem statement literally.

However, in the worst case every fruit scans almost every basket. With n = 100,000, this results in approximately 10^10 operations, which is far beyond acceptable limits.

Key Insight

The challenge is not checking basket capacities. The challenge is efficiently finding the leftmost unused basket whose capacity is at least some threshold.

Suppose we build a segment tree where each node stores the maximum basket capacity in its range among baskets that are still available.

Then:

• If the maximum value in a range is smaller than the fruit quantity, we know no basket in that range can hold the fruit.
• If the maximum value is large enough, then some basket in that range can hold the fruit.

Using this information, we can descend the segment tree:

• Always explore the left child first.
• If the left child contains a valid basket, continue there.
• Otherwise move to the right child.

This guarantees that we find the leftmost available basket whose capacity is large enough.

Once a basket is used, we update its value in the segment tree to 0, effectively removing it from future consideration.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Scan baskets for every fruit
Optimal	O(n log n)	O(n)	Segment tree finds leftmost valid basket efficiently

Algorithm Walkthrough

1. Build a segment tree over the baskets array.

Each node stores the maximum basket capacity within its range. This allows us to quickly determine whether a range contains any basket capable of holding a given fruit. 2. Initialize a counter unplaced = 0.

This will track fruit types that cannot be assigned to any basket. 3. Process each fruit quantity from left to right.

The order is fixed by the problem statement, so we must handle fruits exactly in array order. 4. Check the segment tree root.

If the root maximum is smaller than the fruit quantity, then no available basket can hold this fruit. Increment unplaced and continue. 5. Otherwise search the segment tree.

Starting from the root:

• Examine the left child first.
• If the left child's maximum capacity is large enough, move into the left child.
• Otherwise move into the right child.

This search eventually reaches a leaf corresponding to the leftmost available basket whose capacity is at least the fruit quantity. 6. Mark that basket as used.

Update the leaf value to 0. 7. Recompute segment tree values while returning upward.

Each internal node stores the maximum of its two children. 8. Continue until all fruits have been processed. 9. Return unplaced.

Why it Works

The segment tree maintains the invariant that every node stores the maximum available basket capacity in its range.

If a node's maximum value is smaller than the current fruit quantity, no basket within that range can hold the fruit. Therefore that entire range can safely be ignored.

When searching, we always check the left child before the right child. Whenever the left child contains a valid basket, we continue searching there. Consequently, the first leaf reached is exactly the leftmost available basket capable of holding the fruit.

Because every placement follows the problem's required rule and every used basket is removed from future consideration, the algorithm always produces the correct result.

Python Solution

from typing import List

class Solution:
    def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
        n = len(baskets)

        tree = [0] * (4 * n)

        def build(node: int, left: int, right: int) -> None:
            if left == right:
                tree[node] = baskets[left]
                return

            mid = (left + right) // 2
            build(node * 2, left, mid)
            build(node * 2 + 1, mid + 1, right)

            tree[node] = max(tree[node * 2], tree[node * 2 + 1])

        def update(node: int, left: int, right: int, idx: int) -> None:
            if left == right:
                tree[node] = 0
                return

            mid = (left + right) // 2

            if idx <= mid:
                update(node * 2, left, mid, idx)
            else:
                update(node * 2 + 1, mid + 1, right, idx)

            tree[node] = max(tree[node * 2], tree[node * 2 + 1])

        def find_leftmost(node: int, left: int, right: int, target: int) -> int:
            if left == right:
                return left

            mid = (left + right) // 2

            if tree[node * 2] >= target:
                return find_leftmost(node * 2, left, mid, target)

            return find_leftmost(node * 2 + 1, mid + 1, right, target)

        build(1, 0, n - 1)

        unplaced = 0

        for fruit in fruits:
            if tree[1] < fruit:
                unplaced += 1
                continue

            basket_index = find_leftmost(1, 0, n - 1, fruit)
            update(1, 0, n - 1, basket_index)

        return unplaced

The implementation begins by constructing a segment tree where each node stores the maximum available basket capacity in its interval.

The build function initializes the tree from the basket capacities.

The find_leftmost function performs the crucial search. Because each node stores a maximum value, it can determine whether the left subtree contains a valid basket. If it does, the search continues left. Otherwise, it moves right. This guarantees the leftmost valid basket is found.

After locating a basket, the update function sets that basket's value to zero, indicating that it is no longer available. The maximum values of all affected ancestors are then recomputed.

For every fruit, the root node immediately tells us whether any valid basket still exists. If not, the fruit remains unplaced. Otherwise, we locate and consume the required basket.

Go Solution

func numOfUnplacedFruits(fruits []int, baskets []int) int {
	n := len(baskets)

	tree := make([]int, 4*n)

	var build func(int, int, int)
	build = func(node, left, right int) {
		if left == right {
			tree[node] = baskets[left]
			return
		}

		mid := (left + right) / 2

		build(node*2, left, mid)
		build(node*2+1, mid+1, right)

		if tree[node*2] > tree[node*2+1] {
			tree[node] = tree[node*2]
		} else {
			tree[node] = tree[node*2+1]
		}
	}

	var update func(int, int, int, int)
	update = func(node, left, right, idx int) {
		if left == right {
			tree[node] = 0
			return
		}

		mid := (left + right) / 2

		if idx <= mid {
			update(node*2, left, mid, idx)
		} else {
			update(node*2+1, mid+1, right, idx)
		}

		if tree[node*2] > tree[node*2+1] {
			tree[node] = tree[node*2]
		} else {
			tree[node] = tree[node*2+1]
		}
	}

	var findLeftmost func(int, int, int, int) int
	findLeftmost = func(node, left, right, target int) int {
		if left == right {
			return left
		}

		mid := (left + right) / 2

		if tree[node*2] >= target {
			return findLeftmost(node*2, left, mid, target)
		}

		return findLeftmost(node*2+1, mid+1, right, target)
	}

	build(1, 0, n-1)

	unplaced := 0

	for _, fruit := range fruits {
		if tree[1] < fruit {
			unplaced++
			continue
		}

		idx := findLeftmost(1, 0, n-1, fruit)
		update(1, 0, n-1, idx)
	}

	return unplaced
}

The Go implementation follows the same segment tree design as the Python version. Go slices are used to store the tree, and recursive closures implement build, search, and update operations.

Integer overflow is not a concern because basket capacities are at most 10^9, which comfortably fits within Go's int on LeetCode platforms. The algorithm does not perform arithmetic that could exceed these bounds.

Worked Examples

Example 1

Input

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

Initial segment tree maximum:

max = 5

Fruit	Available Baskets	Chosen Basket	Result
4	[3,5,4]	index 1, capacity 5	placed
2	[3,used,4]	index 0, capacity 3	placed
5	[used,used,4]	none	unplaced

State evolution:

Step	Basket State
Initial	[3,5,4]
After fruit 4	[3,used,4]
After fruit 2	[used,used,4]
After fruit 5	[used,used,4]

Answer:

1

Example 2

Input

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

Fruit	Available Baskets	Chosen Basket	Result
3	[6,4,7]	index 0, capacity 6	placed
6	[used,4,7]	index 2, capacity 7	placed
1	[used,4,used]	index 1, capacity 4	placed

State evolution:

Step	Basket State
Initial	[6,4,7]
After fruit 3	[used,4,7]
After fruit 6	[used,4,used]
After fruit 1	[used,used,used]

Answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Each fruit performs one search and one update
Space	O(n)	Segment tree storage

The segment tree contains O(n) nodes. For each fruit, we perform a root check, a search down the tree, and an update back up the tree. Both search and update require O(log n) time. Since there are n fruits, the total running time is O(n log n).

Test Cases

sol = Solution()

assert sol.numOfUnplacedFruits([4, 2, 5], [3, 5, 4]) == 1  # example 1
assert sol.numOfUnplacedFruits([3, 6, 1], [6, 4, 7]) == 0  # example 2

assert sol.numOfUnplacedFruits([1], [1]) == 0  # single basket fits
assert sol.numOfUnplacedFruits([2], [1]) == 1  # single basket fails

assert sol.numOfUnplacedFruits([5, 5, 5], [5, 5, 5]) == 0  # exact matches

assert sol.numOfUnplacedFruits([10, 10, 10], [1, 2, 3]) == 3  # no basket fits

assert sol.numOfUnplacedFruits([1, 2, 3], [10, 10, 10]) == 0  # all fit

assert sol.numOfUnplacedFruits([4, 4, 4], [4, 3, 4]) == 1  # one fruit unplaced

assert sol.numOfUnplacedFruits([2, 5, 4], [5, 4, 6]) == 0  # leftmost rule matters

assert sol.numOfUnplacedFruits([8, 1, 8], [8, 8, 1]) == 1  # earlier usage affects later fruits

assert sol.numOfUnplacedFruits([1000000000], [1000000000]) == 0  # maximum value

assert sol.numOfUnplacedFruits([7, 7, 7, 7], [7, 7, 7, 7]) == 0  # repeated equal values

Test Summary

Test	Why
[4,2,5], [3,5,4]	Official example 1
[3,6,1], [6,4,7]	Official example 2
[1], [1]	Smallest successful input
[2], [1]	Smallest failing input
Equal capacities and fruits	Exact matching behavior
All fruits too large	No placements possible
All baskets huge	Every fruit can be placed
[4,4,4], [4,3,4]	One placement failure
[2,5,4], [5,4,6]	Validates leftmost selection
[8,1,8], [8,8,1]	Earlier allocations affect later results
Maximum values	Boundary value testing
Repeated values	Duplicate capacities and quantities

Edge Cases

All Fruits Are Too Large

Consider:

fruits = [10, 10, 10]
baskets = [1, 2, 3]

Every fruit exceeds every basket capacity. A buggy implementation might repeatedly search the tree even though placement is impossible. The segment tree root immediately reveals that no valid basket exists, so each fruit is counted as unplaced.

Multiple Valid Baskets Exist

Consider:

fruits = [2]
baskets = [5, 6, 7]

All baskets can hold the fruit. The problem requires choosing the leftmost available basket, which is index 0. The search procedure always prioritizes the left subtree whenever it contains a valid basket, guaranteeing compliance with this rule.

Earlier Placements Affect Later Choices

Consider:

fruits = [8, 1, 8]
baskets = [8, 8, 1]

The first fruit must occupy basket 0 because it is the leftmost valid basket. The second fruit then occupies basket 1, leaving only basket 2 with capacity 1. The final fruit cannot be placed. Any algorithm that attempts to globally optimize basket usage instead of following the required leftmost rule would produce an incorrect result. The segment tree solution exactly simulates the mandated allocation order and therefore handles this situation correctly.