Watch 10 video solutions for Apple Redistribution into Boxes, a easy level problem involving Array, Greedy, Sorting. This walkthrough by codestorywithMIK has 3,321 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 50Problem Overview: You are given two arrays: apple representing apples in each pack and capacity representing the capacity of available boxes. The goal is to redistribute all apples into the minimum number of boxes without exceeding any box’s capacity.
Approach 1: Greedy with Sorting (O(n log n) time, O(1) extra space)
This problem reduces to a simple observation: the total number of apples matters, not which pack they came from. First compute the total apples using a single pass through the apple array. Then sort the capacity array in descending order and keep picking the largest box capacities until their combined capacity can hold all apples. The greedy choice works because using the largest boxes first minimizes the number of boxes required. Sorting dominates the runtime at O(m log m) where m is the number of boxes, while the accumulation step is linear.
The approach relies on concepts commonly used in Greedy strategies: always take the locally optimal choice (largest capacity) to reach a global optimum. Sorting the capacities is what makes the greedy selection straightforward, connecting the solution to patterns from Sorting problems.
Approach 2: Priority Queue (Heap) Selection (O(m log m) time, O(m) space)
Instead of sorting all capacities upfront, push every box capacity into a priority queue and repeatedly extract the largest capacity box until the total capacity covers all apples. Each extraction represents selecting the next best box. If a max‑heap is not directly available, you can simulate it by inserting negative values into a min‑heap. Every heap insertion and removal costs O(log m), resulting in O(m log m) overall time.
This method is useful when capacities arrive dynamically or when you only need the top few elements rather than a fully sorted array. The data structure involved is a Priority Queue, which efficiently retrieves the largest remaining capacity each step.
Recommended for interviews: The greedy sorting approach is what most interviewers expect. It shows you recognize that the order of apple packs is irrelevant and that minimizing boxes simply means selecting the largest capacities first. The heap version demonstrates familiarity with priority queues but is usually unnecessary since sorting is simpler and slightly more memory efficient. Showing the greedy reasoning clearly is the key signal of strong problem‑solving skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Sorting | O(m log m) | O(1) | Best general solution. Simple implementation and minimal memory usage. |
| Priority Queue (Heap) | O(m log m) | O(m) | Useful when capacities arrive dynamically or when repeatedly selecting the largest element. |