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.
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.
The time complexity is O(n times log n), and the space complexity is O(n), where n is the length of baskets.
| 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 |
Fruits Into Baskets II & III | Segment Tree Concepts & Qns | Video 13 | Leetcode 3477 | 3479 | MIK • codestorywithMIK • 17,729 views views
Watch 9 more video solutions →Practice Fruits Into Baskets III with our built-in code editor and test cases.
Practice on FleetCode