Watch 10 video solutions for Maximum Bags With Full Capacity of Rocks, a medium level problem involving Array, Greedy, Sorting. This walkthrough by codestorywithMIK has 6,317 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |