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 <= 109This 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.
Java
C++
C
C#
JavaScript
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.
Java
Time Complexity: O(n log n), predominantly due to building and maintaining the heap.
Space Complexity: O(n), for the heap storage.
| 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. |
Maximum Bags With Full Capacity of Rocks | Leetcode 2279 | Arrays | Contest 294 🔥🔥 • Coding Decoded • 1,578 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