[Medium] 3477. Number of Unplaced Fruits

You are given two integer arrays fruits and baskets.

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

You process fruits from left to right. For each fruit type, you must place it in the leftmost available basket whose capacity is greater than or equal to the fruit’s quantity.

Each basket can hold at most one type of fruit.
If no such basket exists for a fruit type, it remains unplaced.

Return the number of fruit types that are not placed after trying to place all fruits.

Examples

Example 1:

Input: fruits = [4, 2, 5], baskets = [3, 5, 4]
Output: 1
Explanation:
- Fruit 4: Place in leftmost basket with capacity >= 4 → baskets[1] = 5 (placed)
- Fruit 2: Place in leftmost basket with capacity >= 2 → baskets[0] = 3 (placed)
- Fruit 5: Requires capacity >= 5, but remaining basket baskets[2] = 4 < 5 → unplaced
Result: 1 unplaced fruit

Example 2:

Input: fruits = [3, 2, 1], baskets = [1, 2, 3]
Output: 0
Explanation:
- Fruit 3: Place in baskets[2] = 3 (placed)
- Fruit 2: Place in baskets[1] = 2 (placed)
- Fruit 1: Place in baskets[0] = 1 (placed)
Result: 0 unplaced fruits

Constraints

1 <= fruits.length <= 10^5
1 <= baskets.length <= 10^5
1 <= fruits[i] <= 10^9
1 <= baskets[j] <= 10^9

Thinking Process

Segment Tree for Range Max: Efficiently find leftmost index with capacity >= value

Greedy works when local optimal choices lead to global optimum.
Often sort first to make the greedy choice obvious.
Prove or sanity-check: would swapping two choices ever help?

Common Approaches

Typical techniques for this pattern:

Approach	Time	Space	Notes
Sort + greedy (this problem)	O(n log n)	O(1)	Interval scheduling, assignment
Local greedy choice	O(n)	O(1)	Jump game, gas station
Greedy + heap	O(n log n)	O(n)	Merge streams, room allocation
Exchange argument	O(n)	O(1)	Prove greedy choice is safe

Solution

Solution: Segment Tree for Leftmost Query

class SegmentTree:
    def __init__(self, baskets):
        self.n = len(baskets)
        self.tree = [0] * (4 * self.n)
        self.build(1, 0, self.n - 1, baskets)

    def build(self, node, l, r, baskets):
        if l == r:
            self.tree[node] = baskets[l]
        else:
            mid = (l + r) // 2
            self.build(node * 2, l, mid, baskets)
            self.build(node * 2 + 1, mid + 1, r, baskets)
            self.tree[node] = max(self.tree[node * 2], self.tree[node * 2 + 1])

    # Find leftmost index >= l with value >= val
    def query(self, node, l, r, val):
        if self.tree[node] < val:
            return -1  # no basket in this range can hold fruit

        if l == r:
            return l

        mid = (l + r) // 2

        left = self.query(node * 2, l, mid, val)
        if left != -1:
            return left

        return self.query(node * 2 + 1, mid + 1, r, val)

    def update(self, node, l, r, idx):
        if l == r:
            self.tree[node] = 0  # mark basket used
        else:
            mid = (l + r) // 2

            if idx <= mid:
                self.update(node * 2, l, mid, idx)
            else:
                self.update(node * 2 + 1, mid + 1, r, idx)

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


class Solution:
    def numOfUnplacedFruits(self, fruits, baskets):
        n = len(baskets)

        st = SegmentTree(baskets)

        unplaced = 0

        for f in fruits:
            idx = st.query(1, 0, n - 1, f)

            if idx == -1:
                unplaced += 1
            else:
                st.update(1, 0, n - 1, idx)

        return unplaced

Solution Explanation

Approach: Sort + greedy (this problem)

Key idea: 1. Segment Tree for Range Max: Efficiently find leftmost index with capacity >= value

How the code works:

Segment Tree for Range Max: Efficiently find leftmost index with capacity >= value
- Greedy works when local optimal choices lead to global optimum.
- Often sort first to make the greedy choice obvious.
- Prove or sanity-check: would swapping two choices ever help?

Walkthrough — input fruits = [4, 2, 5], baskets = [3, 5, 4], expected output 1:

Fruit 4: Place in leftmost basket with capacity >= 4 → baskets[1] = 5 (placed)
Fruit 2: Place in leftmost basket with capacity >= 2 → baskets[0] = 3 (placed)
Fruit 5: Requires capacity >= 5, but remaining basket baskets[2] = 4 < 5 → unplaced Result: 1 unplaced fruit

Algorithm Explanation:

SegmentTree Class:

Constructor (Lines 5-9):
- Initialize segment tree with size 4 * n
- Build tree from baskets array
build() (Lines 11-20):
- Recursively build segment tree
- Each node stores maximum capacity in its range
- Leaf nodes store individual basket capacities
query() (Lines 22-30):
- Find leftmost index with capacity >= val
- Early Termination: If tree[node] < val, no basket in range can hold fruit → return -1
- Left-First Search: Check left child first to maintain leftmost property
- Base Case: If leaf node and capacity >= val, return index
update() (Lines 32-42):
- Mark basket as used by setting capacity to 0
- Update parent nodes to reflect new maximum

Solution Class:

Main Function (Lines 45-58):
- Build segment tree from baskets
- For each fruit:
  - Query for leftmost basket with capacity >= fruit quantity
  - If found, update basket (mark as used)
  - If not found, increment unplaced count
- Return number of unplaced fruits

How It Works:

Segment Tree Structure: Each node stores maximum capacity in its range
Leftmost Query: By checking left child first, we ensure leftmost index is found
Efficient Updates: After placing fruit, basket capacity becomes 0 (unavailable)
Greedy Matching: Always uses leftmost available basket that fits

Example Walkthrough:

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

Initial Segment Tree:
        [5] (max of [3,5,4])
       /   \
    [5]     [4]
   /   \   /   \
  [3] [5] [4] [0]
   0   1   2   3

Step 1: Process fruit = 4
  query(1, 0, 2, 4):
    - Check left [0,1]: max = 5 >= 4 → explore left
    - Check left [0,0]: max = 3 < 4 → skip
    - Check right [1,1]: max = 5 >= 4 → found at index 1
  Place fruit 4 in basket[1]
  Update: basket[1] = 0
  Tree: [4] (max of [3,0,4])
  
Step 2: Process fruit = 2
  query(1, 0, 2, 2):
    - Check left [0,1]: max = 3 >= 2 → explore left
    - Check left [0,0]: max = 3 >= 2 → found at index 0
  Place fruit 2 in basket[0]
  Update: basket[0] = 0
  Tree: [4] (max of [0,0,4])
  
Step 3: Process fruit = 5
  query(1, 0, 2, 5):
    - Check left [0,1]: max = 0 < 5 → skip
    - Check right [2,2]: max = 4 < 5 → no solution
  No basket found → unplaced++
  
Result: 1 unplaced fruit

Complexity Analysis:

Time Complexity: O(n log m)
- Building segment tree: O(m)
- For each fruit: O(log m) for query + O(log m) for update
- Overall: O(m + n log m) ≈ O(n log m) where n = fruits.length, m = baskets.length
Space Complexity: O(m)
- Segment tree: O(4m) = O(m)
- Other variables: O(1)
- Overall: O(m)
  Common Mistakes

All fruits placed: fruits = [1, 2], baskets = [2, 3] → return 0
No fruits placed: fruits = [5, 6], baskets = [1, 2] → return 2
Exact match: fruits = [3], baskets = [3] → return 0
Single basket: fruits = [1, 2], baskets = [2] → return 1
Large capacities: Handle up to 10^9 values
Not maintaining leftmost order: Using any basket instead of leftmost
Wrong query logic: Not checking left child first
Incorrect update: Not properly updating parent nodes after marking basket used
Off-by-one errors: Incorrect index calculations in segment tree
Not handling duplicates: Same basket capacity appearing multiple times

LC 307: Range Sum Query - Mutable - Segment tree for range queries
LC 850: Rectangle Area II - Segment tree with coordinate compression
LC 699: Falling Squares - Segment tree for range max updates
LC 715: Range Module - Segment tree for interval operations

Key Takeaways

Segment Tree for Range Max: Efficiently find leftmost index with capacity >= value
Left-First Traversal: Check left child first to maintain leftmost property
Greedy Matching: Always use leftmost available basket
Update Strategy: Mark basket as used by setting capacity to 0
Early Termination: If max capacity in range < required, skip entire range

References

LC 3477: Number of Unplaced Fruits on LeetCode
LeetCode Discuss — LC 3477: Number of Unplaced Fruits
LeetCode Editorial (may require premium)

Template Reference

Array & Matrix

Robina Li

[Medium] 3477. Number of Unplaced Fruits

Examples

Constraints

Thinking Process

Common Approaches

Solution

Solution: Segment Tree for Leftmost Query

Solution Explanation

Algorithm Explanation:

SegmentTree Class:

Solution Class:

How It Works:

Example Walkthrough:

Complexity Analysis:

Common Mistakes

Key Takeaways

References

Template Reference

Related Posts

Recent Posts

Examples

Constraints

Thinking Process

Common Approaches

Solution

Solution: Segment Tree for Leftmost Query

Solution Explanation

Algorithm Explanation:

SegmentTree Class:

Solution Class:

How It Works:

Example Walkthrough:

Complexity Analysis:

Common Mistakes

Related Problems

Key Takeaways

References

Template Reference

Related Posts

Recent Posts