#3479

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Fruits Into Baskets III

Fruits Into Baskets III requires placing fruits into baskets efficiently using binary search over the answer space for correct allocation.

array binary search segment tree ordered set

Problem Statement

You are given two arrays, fruits and baskets, each of length n. fruits[i] indicates the quantity of the ith fruit type, while baskets[j] shows the capacity of the jth basket. From left to right, attempt to place each fruit type into the baskets according to their capacities, ensuring no basket exceeds its limit.

Return the number of fruit types that remain unplaced after attempting all allocations. For example, given fruits = [4,2,5] and baskets = [3,5,4], one fruit type cannot be placed, so the output is 1. Consider optimizing the process using binary search over the valid allocation space to determine feasible placement efficiently.

Examples

Example 1

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

Output: 1

Since one fruit type remains unplaced, we return 1.

Example 2

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

Output: 0

Since all fruits are successfully placed, we return 0.

Constraints

n == fruits.length == baskets.length
1 <= n <= 105
1 <= fruits[i], baskets[i] <= 109

Solution Approach

Sort and Prepare Baskets

Sort baskets by their capacity and original index to streamline allocation. This ordering helps when applying binary search and segment trees for placement verification.

Binary Search Over Maximum Placeable Fruits

Use binary search to identify the largest number of fruits that can be allocated without violating basket capacities. Check each candidate value using the segment tree to track remaining space efficiently.

Count Unplaced Fruit Types

After verifying allocations, count fruit types that could not fit into any basket. Maintain an ordered set or segment tree to quickly query available capacities and update remaining baskets during the allocation process.

Complexity Analysis

Metric	Value
Time	O(n \log n)
Space	O(n)

Time complexity is O(n log n) due to sorting and binary search across n fruit types. Space complexity is O(n) for segment tree or ordered set storage used to track basket capacities and remaining fruits.

What Interviewers Usually Probe

Sorting baskets hints at using structured allocation and binary search validation.
Ask about handling unplaced fruits efficiently, testing segment tree or ordered set use.
Check candidate maximum fruit placement with binary search over feasible answers.

Common Pitfalls or Variants

Common pitfalls

Failing to sort baskets before binary search can lead to incorrect placements.
Not updating basket capacities after each allocation causes overcounting or misplacement.
Confusing array indices when combining original positions with sorted capacities.

Follow-up variants

Allow partial placement of a fruit type, requiring tracking leftover quantities per basket.
Maximize total fruits placed rather than minimizing unplaced types.
Change pattern to allow multiple fruit types per basket with combined capacities.

FAQ

What is the main strategy for Fruits Into Baskets III?

Use binary search over the maximum placeable fruits, sorting baskets and checking allocations efficiently with a segment tree or ordered set.

Can baskets have the same capacity?

Yes, baskets can share capacities, so sorting by capacity and index ensures correct allocation order.

Why not just fill baskets greedily from left to right?

Greedy filling can fail to minimize unplaced fruit types; binary search over allocation space guarantees optimal counting.

How does the segment tree help in this problem?

Segment tree allows querying and updating available basket capacities quickly during allocation checks in binary search.

What interview pattern does this problem demonstrate?

It demonstrates binary search over a valid answer space, combined with array sorting and segment tree updates for feasibility checks.

terminal

Solution

Solution 1: Segment Tree Binary Search

We can use a segment tree to maintain the maximum basket capacity in an interval, which allows us to quickly find the first basket with capacity greater than or equal to the fruit quantity through binary search. If no such basket is found, we increment the answer by one; if found, we set that basket's capacity to zero, indicating that the basket has been used.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

class SegmentTree:
    __slots__ = ["nums", "tr"]

    def __init__(self, nums):
        self.nums = nums
        n = len(nums)
        self.tr = [0] * (n << 2)
        self.build(1, 1, n)

    def build(self, u, l, r):
        if l == r:
            self.tr[u] = self.nums[l - 1]
            return
        mid = (l + r) >> 1
        self.build(u << 1, l, mid)
        self.build(u << 1 | 1, mid + 1, r)
        self.pushup(u)

    def modify(self, u, l, r, i, v):
        if l == r:
            self.tr[u] = v
            return
        mid = (l + r) >> 1
        if i <= mid:
            self.modify(u << 1, l, mid, i, v)
        else:
            self.modify(u << 1 | 1, mid + 1, r, i, v)
        self.pushup(u)

    def query(self, u, l, r, v):
        if self.tr[u] < v:
            return -1
        if l == r:
            return l
        mid = (l + r) >> 1
        if self.tr[u << 1] >= v:
            return self.query(u << 1, l, mid, v)
        return self.query(u << 1 | 1, mid + 1, r, v)

    def pushup(self, u):
        self.tr[u] = max(self.tr[u << 1], self.tr[u << 1 | 1])


class Solution:
    def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
        tree = SegmentTree(baskets)
        n = len(baskets)
        ans = 0
        for x in fruits:
            i = tree.query(1, 1, n, x)
            if i < 0:
                ans += 1
            else:
                tree.modify(1, 1, n, i, 0)
        return ans

Continue Practicing

#3477 fruits into baskets ii #2659 make array empty #3501 maximize active section with trade ii