You have n bags numbered from 0 to n - 1. You are given two 0-indexed integer arrays capacity and rocks. The ith bag can hold a maximum of capacity[i] rocks and currently contains rocks[i] rocks. You are also given an integer additionalRocks, the number of additional rocks you can place in any of the bags.
Return the maximum number of bags that could have full capacity after placing the additional rocks in some bags.
Example 1:
Input: capacity = [2,3,4,5], rocks = [1,2,4,4], additionalRocks = 2 Output: 3 Explanation: Place 1 rock in bag 0 and 1 rock in bag 1. The number of rocks in each bag are now [2,3,4,4]. Bags 0, 1, and 2 have full capacity. There are 3 bags at full capacity, so we return 3. It can be shown that it is not possible to have more than 3 bags at full capacity. Note that there may be other ways of placing the rocks that result in an answer of 3.
Example 2:
Input: capacity = [10,2,2], rocks = [2,2,0], additionalRocks = 100 Output: 3 Explanation: Place 8 rocks in bag 0 and 2 rocks in bag 2. The number of rocks in each bag are now [10,2,2]. Bags 0, 1, and 2 have full capacity. There are 3 bags at full capacity, so we return 3. It can be shown that it is not possible to have more than 3 bags at full capacity. Note that we did not use all of the additional rocks.
Constraints:
n == capacity.length == rocks.length1 <= n <= 5 * 1041 <= capacity[i] <= 1090 <= rocks[i] <= capacity[i]1 <= additionalRocks <= 109Problem Overview: You are given arrays capacity and rocks where each bag has a maximum capacity and a current number of rocks. You also have additionalRocks to distribute. The goal is to maximize how many bags reach full capacity after distributing these extra rocks.
The key observation: every bag requires a certain number of additional rocks to become full. If you always fill the bags that require the fewest extra rocks first, you maximize the number of completed bags.
Approach 1: Greedy with Sorting (O(n log n) time, O(n) space)
Compute how many rocks each bag still needs: required[i] = capacity[i] - rocks[i]. Store these values in an array and sort it in ascending order. Then iterate through the sorted requirements and greedily fill the cheapest bags first. For each requirement, subtract it from additionalRocks. If enough rocks remain, the bag becomes full and the count increases; otherwise stop. Sorting ensures you always prioritize the smallest deficits, which maximizes the number of bags filled. This approach uses ideas from greedy algorithms and sorting, and works well because the cost of filling each bag is independent.
Approach 2: Priority Queue (Min-Heap) (O(n log n) time, O(n) space)
Instead of sorting all deficits upfront, push each required value into a min-heap. A min-heap always exposes the smallest deficit at the top. Repeatedly pop the smallest value and check whether additionalRocks can cover it. If yes, subtract it and increment the number of full bags. If not, stop because every remaining bag requires at least as many rocks. The heap approach models the same greedy decision but retrieves the next best candidate dynamically. It relies on a heap structure and is conceptually useful when data arrives incrementally or when you want explicit priority ordering.
Recommended for interviews: The greedy sorting solution is typically what interviewers expect. It shows you recognized the optimization strategy: fill the smallest deficits first. Implementing it with a sorted array is simple and efficient at O(n log n). The heap approach demonstrates familiarity with priority queues, but it adds extra structure without improving asymptotic complexity.
This problem is a classic greedy allocation pattern: compute cost differences, sort them, and spend limited resources in the most efficient order. Similar reasoning appears frequently in array optimization problems.
This approach involves calculating how many rocks each bag needs to be full. Then, we sort these requirements in increasing order. By doing so, we ensure we fill the bags requiring fewer rocks first, maximizing the number of fully filled bags. We iterate through these sorted requirements, and while we have enough additional rocks, we fill these bags, counting the number of bags that can be fully filled.
This Python function calculates the number of rocks needed for each bag, sorts these requirements, then iteratively fills as many bags as possible using the given additional rocks, counting how many bags achieve full capacity.
Time Complexity: O(n log n), due to sorting the differences.
Space Complexity: O(n), for storing the differences array.
Instead of sorting the entire list of differences, we can use a min-heap (priority queue) to keep track of the current smallest difference that can be fulfilled with the additional rocks. This way, we continuously fill the bags requiring the least rocks at the minimum overhead cost of tree-based structure operations. While more sophisticated, this method matches the efficiency of the sorting approach for this problem's expected input size.
This solution uses a min-heap to efficiently decide which bags to fill with additional rocks by always selecting the currently least required amount, popping it from the heap and counting the full bag if successfully filled.
Time Complexity: O(n log n), predominantly due to building and maintaining the heap.
Space Complexity: O(n), for the heap storage.
First, we calculate the remaining capacity of each bag, then sort the remaining capacities. Next, we traverse the remaining capacities from smallest to largest, putting the extra stones into the bags until the extra stones are used up or the remaining capacities of the bags are exhausted. Finally, we return the number of bags at this point.
Time complexity is O(n times log n), and space complexity is O(log n). Here, n is the number of bags.
| Approach | Complexity |
|---|---|
| Greedy Approach with Sorting | Time Complexity: O(n log n), due to sorting the differences. |
| Priority Queue (Min-Heap) Approach | Time Complexity: O(n log n), predominantly due to building and maintaining the heap. |
| Sorting + Greedy | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Sorting | O(n log n) | O(n) | Best general solution. Sort deficits and greedily fill smallest requirements first. |
| Priority Queue (Min-Heap) | O(n log n) | O(n) | Useful when processing bags dynamically or when explicit priority ordering is preferred. |
Maximum Bags With Full Capacity of Rocks : Explanation ➕ Live Coding 🧑🏻💻👩🏻💻 • codestorywithMIK • 6,317 views views
Watch 9 more video solutions →Practice Maximum Bags With Full Capacity of Rocks with our built-in code editor and test cases.
Practice on FleetCode