You are given an array apple of size n and an array capacity of size m.
There are n packs where the ith pack contains apple[i] apples. There are m boxes as well, and the ith box has a capacity of capacity[i] apples.
Return the minimum number of boxes you need to select to redistribute these n packs of apples into boxes.
Note that, apples from the same pack can be distributed into different boxes.
Example 1:
Input: apple = [1,3,2], capacity = [4,3,1,5,2] Output: 2 Explanation: We will use boxes with capacities 4 and 5. It is possible to distribute the apples as the total capacity is greater than or equal to the total number of apples.
Example 2:
Input: apple = [5,5,5], capacity = [2,4,2,7] Output: 4 Explanation: We will need to use all the boxes.
Constraints:
1 <= n == apple.length <= 501 <= m == capacity.length <= 501 <= apple[i], capacity[i] <= 50In #3074 Apple Redistribution into Boxes, the goal is to determine the minimum number of boxes needed to store all apples given each box's capacity. The key observation is that we only care about the total number of apples and how efficiently we can use available box capacities.
A common strategy is to use a greedy approach. First compute the total apples using a simple traversal of the apples array. Then consider the capacities of the boxes. To minimize the number of boxes used, it is beneficial to utilize the largest capacities first. Sorting the box capacities in descending order allows us to keep adding capacity until the total storage covers all apples.
This approach works because choosing larger boxes earlier reduces the number of selections required. Sorting dominates the runtime, giving an overall time complexity of O(m log m), where m is the number of boxes, while the space usage can remain O(1) if sorting is done in place.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy with Sorting (use largest boxes first) | O(m log m) | O(1) extra (in-place sort) |
Greg Hogg
Use these hints if you're stuck. Try solving on your own first.
Sort array <code>capacity</code> in non-decreasing order.
Greedily select boxes with the largest capacities to redistribute apples optimally.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Sorting helps process box capacities from largest to smallest. This ensures that the largest storage options are used first, which minimizes the number of boxes required.
Yes, problems like this are common in interviews because they test greedy thinking, array manipulation, and basic optimization strategies. Variations of capacity allocation problems often appear in technical interviews.
Arrays are sufficient for this problem since both apples and box capacities are provided as arrays. Sorting the boxes array enables the greedy strategy to work efficiently.
The optimal approach uses a greedy strategy. Compute the total number of apples and then prioritize boxes with the largest capacities so fewer boxes are needed to cover the total.