Watch 10 video solutions for Fruits Into Baskets III, a medium level problem involving Array, Binary Search, Segment Tree. This walkthrough by codestorywithMIK has 17,729 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given two arrays of integers, fruits and baskets, each of length n, where fruits[i] represents the quantity of the ith type of fruit, and baskets[j] represents the capacity of the jth basket.
From left to right, place the fruits according to these rules:
Return the number of fruit types that remain unplaced after all possible allocations are made.
Example 1:
Input: fruits = [4,2,5], baskets = [3,5,4]
Output: 1
Explanation:
fruits[0] = 4 is placed in baskets[1] = 5.fruits[1] = 2 is placed in baskets[0] = 3.fruits[2] = 5 cannot be placed in baskets[2] = 4.Since one fruit type remains unplaced, we return 1.
Example 2:
Input: fruits = [3,6,1], baskets = [6,4,7]
Output: 0
Explanation:
fruits[0] = 3 is placed in baskets[0] = 6.fruits[1] = 6 cannot be placed in baskets[1] = 4 (insufficient capacity) but can be placed in the next available basket, baskets[2] = 7.fruits[2] = 1 is placed in baskets[1] = 4.Since all fruits are successfully placed, we return 0.
Constraints:
n == fruits.length == baskets.length1 <= n <= 1051 <= fruits[i], baskets[i] <= 109Problem Overview: You are given an array of fruits where each value represents the size of a fruit, and an array of baskets where each value represents the basket capacity. Each fruit must go into the leftmost basket with capacity greater than or equal to the fruit size. A basket can only hold one fruit. If no such basket exists, the fruit cannot be placed. Return the number of fruits successfully placed.
Approach 1: Brute Force Simulation (O(n * m) time, O(1) space)
Process fruits from left to right. For each fruit, iterate through the baskets array and pick the first unused basket whose capacity is greater than or equal to the fruit size. Mark the basket as used and continue. This approach directly simulates the rule but performs a linear scan for every fruit, resulting in O(n * m) time in the worst case. It works for small inputs but quickly becomes too slow when both arrays grow large.
Approach 2: Segment Tree + Binary Search (O((n + m) log m) time, O(m) space)
Build a segment tree over the baskets array where each node stores the maximum capacity in that range. For each fruit, query the tree to find the leftmost index whose capacity is at least the fruit size. This is done with a tree-guided binary search: if the left child’s maximum is large enough, recurse left; otherwise move to the right child. Once a basket is used, update that index in the tree to -inf (or 0) so it cannot be selected again. Each query and update costs O(log m), making the full algorithm O((n + m) log m). This handles large constraints efficiently.
Approach 3: Ordered Set / Balanced BST (O((n + m) log m) time, O(m) space)
Another option uses an ordered set or balanced BST storing basket indices grouped by capacity. As fruits arrive, you search for the first basket with capacity ≥ fruit size and remove it after assignment. This approach achieves similar complexity to the segment tree solution but depends on language support for ordered structures and efficient lower-bound queries.
Recommended for interviews: The segment tree approach is typically expected. The brute force simulation shows you understand the placement rule, but the optimized solution demonstrates knowledge of range queries and tree-guided searches. It cleanly finds the leftmost valid basket while supporting fast updates after each assignment.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n * m) | O(1) | Small input sizes or when demonstrating the basic placement rule |
| Segment Tree Binary Search | O((n + m) log m) | O(m) | General case with large constraints and frequent range queries |
| Ordered Set / Balanced BST | O((n + m) log m) | O(m) | Languages with strong ordered-set support and efficient lower_bound operations |