Fruits Into Baskets II
EasyPrompt
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:
- Each fruit type must be placed in the leftmost available basket with a capacity greater than or equal to the quantity of that fruit type.
- Each basket can hold only one type of fruit.
- If a fruit type cannot be placed in any basket, it remains unplaced.
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] = 4is placed inbaskets[1] = 5.fruits[1] = 2is placed inbaskets[0] = 3.fruits[2] = 5cannot be placed inbaskets[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] = 3is placed inbaskets[0] = 6.fruits[1] = 6cannot be placed inbaskets[1] = 4(insufficient capacity) but can be placed in the next available basket,baskets[2] = 7.fruits[2] = 1is placed inbaskets[1] = 4.
Since all fruits are successfully placed, we return 0.
Constraints:
n == fruits.length == baskets.length1 <= n <= 1001 <= fruits[i], baskets[i] <= 1000
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. We iterate through each fruit type and, for each one, we perform a linear scan through the baskets from left to right to find the first available basket with sufficient capacity.
Algorithm
- Initialize a boolean array
usedBasketsof sizento allfalseto track basket availability. - Initialize
placedCount = 0. - Iterate through each
fruitin thefruitsarray from left to right. - For each
fruit, start an inner loop to iterate through thebasketsarray from indexj = 0ton-1. - Inside the inner loop, check if the current basket
jis not used (!usedBaskets[j]) and has sufficient capacity (baskets[j] >= fruit). - If both conditions are met, it means we've found the leftmost available basket. Mark it as used (
usedBaskets[j] = true), incrementplacedCount, andbreakthe inner loop to proceed to the next fruit. - After iterating through all fruits, the number of unplaced fruits is
n - placedCount.
Walkthrough
We use a boolean array, usedBaskets, to keep track of which baskets have already been assigned a fruit type.
For each fruit f from the fruits array:
- We search for a suitable basket by iterating through the
basketsarray from index 0 ton-1. - The first basket
jwe encounter that is not yet used (usedBaskets[j]is false) and has enough capacity (baskets[j] >= f) is chosen. - We mark this basket as used by setting
usedBaskets[j] = trueand move on to the next fruit. - If we iterate through all the baskets and don't find a suitable one for the current fruit, we count it as unplaced.
This process is repeated for all fruit types. The total count of unplaced fruits is the final answer.
class Solution { public int unplacedFruits(int[] fruits, int[] baskets) { int n = fruits.length; boolean[] usedBaskets = new boolean[n]; int placedCount = 0; for (int fruit : fruits) { for (int j = 0; j < n; j++) { if (!usedBaskets[j] && baskets[j] >= fruit) { usedBaskets[j] = true; placedCount++; break; // Found the leftmost basket, move to the next fruit } } } return n - placedCount; }}Complexity
Time
O(n^2), where `n` is the number of fruits. The nested loops lead to a quadratic time complexity, as for each of the `n` fruits, we might scan up to `n` baskets in the worst case.
Space
O(n), where `n` is the number of baskets. This is for the `usedBaskets` boolean array.
Trade-offs
Pros
Simple to understand and implement.
Directly models the logic from the problem statement.
Efficient enough for the given constraints where
n <= 100.
Cons
The O(n^2) time complexity can be slow if the input size
nis very large.
To improve upon the O(n^2) complexity, we can optimize the search for a suitable basket. The bottleneck in the brute-force approach is the linear scan for each fruit. We can use a segment tree data structure to find the leftmost available basket with sufficient capacity in logarithmic time.
Algorithm
- Define a segment tree data structure where each node stores the maximum value in its corresponding index range.
- Build: Construct the segment tree from the
basketsarray. This takesO(n)time. - Initialize
unplacedCount = 0. - Iterate through each
fruitin thefruitsarray. - Query: For each
fruit, query the segment tree to find the leftmost indexjwhere the capacity is sufficient (>= fruit). This query must be designed to explore the left side of the tree first to respect the 'leftmost' rule. This operation takesO(log n). - Update: If a basket at index
jis found, update the tree by setting the capacity atjto 0 (or another value that won't be chosen again). This prevents the basket from being used for subsequent fruits and takesO(log n). - If the query finds no suitable basket, increment
unplacedCount. - Return the final
unplacedCount.
Walkthrough
A segment tree is built over the baskets array. Each node in the tree stores the maximum capacity within its corresponding index range.
When we need to place a fruit f, we query the segment tree:
- Query: We search for the leftmost index
jsuch thatbaskets[j] >= f. The query traverses the tree from the root, always prioritizing the left child (which corresponds to smaller indices) to satisfy the "leftmost" requirement. This search operation takes O(log n) time. - Update: If a suitable basket at index
jis found, we "remove" it to prevent it from being used again. This is done by updating its value in the segment tree to a value that will never satisfy the condition (e.g., 0, since capacities are positive). This update also takes O(log n) time.
If the query returns no suitable basket, the fruit is marked as unplaced. By replacing the O(n) linear scan with an O(log n) segment tree query and update, we reduce the overall time complexity.
class Solution { int[] tree; int[] baskets; int n; // Build the segment tree private void build(int node, int start, int end) { if (start == end) { tree[node] = baskets[start]; } else { int mid = start + (end - start) / 2; build(2 * node, start, mid); build(2 * node + 1, mid + 1, end); tree[node] = Math.max(tree[2 * node], tree[2 * node + 1]); } } // Update the tree after using a basket private void update(int node, int start, int end, int idx, int val) { if (start == end) { tree[node] = val; } else { int mid = start + (end - start) / 2; if (start <= idx && idx <= mid) { update(2 * node, start, mid, idx, val); } else { update(2 * node + 1, mid + 1, end, idx, val); } tree[node] = Math.max(tree[2 * node], tree[2 * node + 1]); } } // Query for the leftmost basket with capacity >= fruit private int query(int node, int start, int end, int fruit) { if (tree[node] < fruit) { return -1; // No basket in this range has enough capacity } if (start == end) { return start; // Leaf node, found a suitable basket } int mid = start + (end - start) / 2; // Prioritize left child for "leftmost" if (tree[2 * node] >= fruit) { int res = query(2 * node, start, mid, fruit); if (res != -1) return res; } // If left child has no suitable basket, check right child return query(2 * node + 1, mid + 1, end, fruit); } public int unplacedFruits(int[] fruits, int[] baskets) { this.n = baskets.length; this.baskets = baskets; this.tree = new int[4 * n]; build(1, 0, n - 1); int unplacedCount = 0; for (int fruit : fruits) { int basketIndex = query(1, 0, n - 1, fruit); if (basketIndex == -1) { unplacedCount++; } else { // Mark basket as used by setting its capacity to 0 update(1, 0, n - 1, basketIndex, 0); } } return unplacedCount; }}Complexity
Time
O(n log n). Building the tree takes O(n). For each of the `n` fruits, we perform one query and one update, both of which take O(log n) time.
Space
O(n), where `n` is the number of baskets. The segment tree requires an auxiliary array of size approximately `4n`.
Trade-offs
Pros
Highly efficient with a time complexity of O(n log n).
Scales well for larger input sizes beyond the problem's constraints.
Demonstrates the use of advanced data structures to optimize search problems.
Cons
Significantly more complex to implement and debug compared to the brute-force approach.
The overhead of the segment tree might make it slightly slower than the simple O(n^2) solution for the small constraints of this problem (
n <= 100).
Solutions
Solution
class Solution {public int numOfUnplacedFruits(int[] fruits, int[] baskets) { int n = fruits.length; boolean[] vis = new boolean[n]; int ans = n; for (int x : fruits) { for (int i = 0; i < n; ++i) { if (baskets[i] >= x && !vis[i]) { vis[i] = true; --ans; break; } } } return ans; }}class Solution {public: int numOfUnplacedFruits(vector<int> &fruits, vector<int> &baskets) { int n = fruits.size(); vector<bool> vis(n); int ans = n; for (int x : fruits) { for (int i = 0; i < n; ++i) { if (baskets[i] >= x && !vis[i]) { vis[i] = true; --ans; break; } } } return ans; }};class Solution: def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int: n = len(fruits) vis = [False] * n ans = n for x in fruits: for i, y in enumerate(baskets): if y >= x and not vis[i]: vis[i] = True ans -= 1 break return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.