Fruits Into Baskets III

Fruits Into Baskets III

What is this problem about?

The Fruits Into Baskets III interview question is identical in structure to "Fruits Into Baskets II". You are given an array of fruit quantities and an array of basket capacities. For each fruit, you must find the first basket (lowest index) that can hold it, and then mark that basket as used. You return the number of unplaced fruits. The difference is usually in the constraints: Version III typically has much larger input sizes, strictly requiring an $O(N \log N)$ solution.

Why is this asked in interviews?

This is a classic "Hard" problem asked by companies like Bloomberg and Amazon to filter candidates based on their mastery of advanced data structures. The Segment Tree interview pattern is absolutely mandatory here. It tests not just the knowledge of the data structure, but the ability to implement a custom query logic (finding the first valid index rather than just a range max/sum) efficiently.

Algorithmic pattern used

This problem relies entirely on a Segment Tree for Range Maximum Queries.

1. Build: Construct a segment tree where each node holds the maximum value of the baskets array in its represented range.
2. Query & Update: For a fruit of size x:
   • Start at the root. If tree[root] < x, return -1 (cannot be placed).
   • If the left child's maximum is $\ge x$, recurse into the left child.
   • Otherwise, recurse into the right child.
   • When reaching a leaf node, this is the first valid basket. Update its capacity to 0 and propagate the change upwards to maintain the max values.

Example explanation

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

1. Segment Tree (Max): Root represents [0, 2] with max 5. Left child [0, 1] max 5, Right child [2, 2] max 4.
2. Fruit 4:
   • Root max (5) $\ge 4$. Check left child.
   • Left child max (5) $\ge 4$. Check its left child (leaf 0, val 3). $3 < 4$.
   • Check its right child (leaf 1, val 5). $5 \ge 4$.
   • Basket 1 takes it. Update leaf 1 to 0. Root max becomes 4.
3. Fruit 2:
   • Root max (4) $\ge 2$. Check left.
   • Left max (3) $\ge 2$. Check its left (leaf 0, val 3). $3 \ge 2$.
   • Basket 0 takes it. Update leaf 0 to 0. Root max becomes 4 (from leaf 2).
4. Fruit 5:
   • Root max (4) $< 5$. Cannot place. Result: 1 unplaced.

Common mistakes candidates make

• Binary Search on array: Sorting the baskets array destroys the "first available" (lowest index) requirement.
• Inefficient Updates: Rebuilding the entire Segment Tree instead of doing a point update, which turns $O(\log N)$ into $O(N)$.
• Memory limits: Using an array representation of a segment tree that is too large (should be $4 imes N$).

Interview preparation tip

Segment Trees can be intimidating to write from scratch during an interview. Practice a template for Point Update and Range Max Query. Focus specifically on the logic for routing the search to the left or right child based on the left child's maximum value.