Practice Maximum Bags With Full Capacity of Rocks
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
Problem Statement
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.
Source: Maximum Bags With Full Capacity of Rocks on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
capacity = [2,3,4,5], rocks = [1,2,4,4], additionalRocks = 2
3
Subtract rocks from capacity to get the remaining spaces [1, 1, 0, 1]. Bag 2 is already full and needs no additional rock. The two extra rocks can fill any two of the three bags that each need one, giving three full bags altogether. Filling all four would require three extra rocks. Sorting these deficits and paying the smallest ones first maximizes the number of completed bags; the original capacities alone do not determine the best order.
# Example 2
capacity = [10,2,2], rocks = [2,2,0], additionalRocks = 100
3
The deficits are [8, 0, 2]. The middle bag is already full, and filling the other two costs 8 + 2 = 10 rocks. Since 100 rocks are available, all three bags can be full and 90 rocks remain unused. The task does not require using every additional rock, and the answer cannot exceed the number of bags. Count zero-deficit bags even before spending the budget.
Constraints
How to solve Maximum Bags With Full Capacity of Rocks
Original notes for interview preparation, written for this problem. Reviewed .
Key insight
Each bag has a fixed deficit, capacity minus rocks, and the objective counts bags rather than rocks, so filling the cheapest deficits first is optimal: any solution that fills an expensive bag while skipping a cheaper one can swap them without losing a bag and while saving rocks.
Why brute force is not enough
Trying every subset of bags and checking whether its total deficit fits within additionalRocks costs O(2^n), and n can be 5 * 10^4. Enumerating subsets by size with pruning is still exponential in the worst case.
Approach
- Compute each bag's remaining space as capacity[i] minus rocks[i]. Bags whose space is already zero are full and will be counted without spending anything.
- Sort the deficits in nondecreasing order. The exchange argument guarantees that some optimal choice of bags is a prefix of this sorted order.
- Walk the sorted deficits, subtracting each from the remaining budget while it fits and incrementing the count of full bags. The invariant is that every bag seen so far that could be afforded has been filled.
- Stop at the first deficit that exceeds the remaining budget, since all later deficits are at least as large, and return the count. Leftover rocks are simply unused.
Walkthrough of Example 1
capacity = [2,3,4,5], rocks = [1,2,4,4], additionalRocks = 2 → 3
- Deficits are 2-1, 3-2, 4-4 and 5-4, giving [1, 1, 0, 1].
- Sorted they become [0, 1, 1, 1], and the budget is 2.
- Take 0: count 1, budget still 2. Take 1: count 2, budget 1. Take 1: count 3, budget 0.
- The remaining deficit 1 exceeds the budget 0, so the scan stops and the answer is 3.
Time and space
Time O(n log n) · Space O(n). Sorting the n deficits dominates the single linear pass; the deficit array is the only linear extra storage, and it can be avoided by overwriting an input array if allowed.
Interview pitfalls
- Sorting by capacity or by current rocks instead of by deficit; only the size of the gap matters for the greedy.
- Skipping bags whose deficit is zero or charging them one rock; they are already full and must be counted.
- Accumulating deficits in 32-bit arithmetic: each value can be 10^9, so a running sum over many bags overflows.
- Continuing past the first unaffordable deficit hoping a later one fits; sorted order guarantees none does.
- Returning the number of rocks placed or the unused budget rather than the number of full bags.
Follow-up questions interviewers ask
- If placing a rock in bag i had a bag-specific cost, how would the selection change and would a simple greedy still be optimal?
- How would you maintain the answer as bags arrive one at a time, using a heap keyed by deficit?
- What if rocks may also be moved between bags, so overfull bags can donate to others?
Further reading on the technique: Greedy algorithm
Related LeetCode Problems
Practice more problems similar to Maximum Bags With Full Capacity of Rocks.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.