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.
This approach suggests sorting the box capacities in descending order and continuously filling the boxes until all apple packs are distributed. The greedy nature ensures we utilize boxes with maximum capacity first, minimizing the total number of boxes used.
This C function uses a greedy algorithm. First, it calculates the total number of apples, then sorts the capacity array in descending order. It iteratively subtracts the largest available box capacity from the total apple count, until all apples are redistributed. The number of iterations gives the minimum number of boxes used.
Time Complexity: O(m log m) due to sorting, and O(m) for iterating over the boxes. Total is O(m log m).
Space Complexity: O(1), as the sorting is done in place.
This approach is alternative to the greedy method, which leverages a priority queue (min-heap) to manage capacities and ensures that the smallest required boxes are filled first. This can be useful in scenarios where random access to the smallest element is necessary. Although it may not be optimal for the current arrangement, it provides a perspective on alternative sorting.
In C++, the standard library provides a priority queue, which can be used for managing smallest elements efficiently. The code leverages this to consistently use the smallest box capacity still needed and adjusts the total until all apples are distributed.
Time Complexity: O(m log m) for heap management operations.
Space Complexity: O(m) since space is required for the priority queue.
To minimize the number of boxes needed, we should prioritize using boxes with larger capacities. Therefore, we can sort the boxes in descending order of capacity, and then use the boxes one by one until all the apples are packed. We return the number of boxes used at this point.
The time complexity is O(m times log m + n) and the space complexity is O(log m), where m and n are the lengths of the arrays capacity and apple respectively.
| Approach | Complexity |
|---|---|
| Greedy Approach for Minimizing Box Usage | Time Complexity: O(m log m) due to sorting, and O(m) for iterating over the boxes. Total is O(m log m). |
| Use of Priority Queue (Min-Heap Structure) | Time Complexity: O(m log m) for heap management operations. |
| Greedy + Sorting | — |
| 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. |
Apple Redistribution into Boxes | Simple Explanation | Homework Inside | Leetcode 3074 | MIK • codestorywithMIK • 3,321 views views
Watch 9 more video solutions →Practice Apple Redistribution into Boxes with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor