Maximum Bags With Full Capacity of Rocks — Solution

Problem

You have a collection of bags, each with a fixed capacity and some rocks already inside. You're given a pool of additional rocks you can distribute however you like. Find the maximum number of bags you can completely fill.

Example:

• Input: capacity = [2, 3, 4, 5], rocks = [1, 2, 4, 4], additionalRocks = 2
• Output: 3
• Explanation: The remaining space per bag is [1, 1, 0, 1]. We can fill the bag that already needs 0 rocks for free, then spend 1 rock on each of two more bags, totaling 3 fully filled bags.

Counter-example: If we greedily filled the largest-capacity bag first (space = 1, then space = 1, then space = 1 — wait, same here), consider capacity = [10, 2], rocks = [0, 1], additionalRocks = 1: remaining is [10, 1]. Filling the 10-space bag wastes all 1 rock with nothing to show; filling the 1-space bag completes it. Greedy by smallest-space-first gives 1 bag; greedy by largest-capacity gives 0.

Intuition

Each additional rock you spend "buys" progress toward filling one bag. To maximize the number of fully filled bags, you want each rock you spend to go as far as possible — which means completing the bags that are closest to full first. Sorting bags by their remaining space and filling greedily from smallest to largest guarantees you never waste a rock on a bag you could have completed with fewer.

Solution — Greedy Sort

Compute how many rocks each bag still needs, sort those needs ascending, then spend your rocks on the cheapest bags first until you run out.

1. For each bag, compute its remaining space: space[i] = capacity[i] - rocks[i].
2. Sort all remaining spaces in ascending order (cheapest bags first).
3. Iterate through the sorted spaces. If additionalRocks >= space, fill the bag: subtract space from additionalRocks and increment the count.
4. If additionalRocks < space, you cannot fill this bag or any subsequent one (since they are at least as expensive). Stop immediately.
5. Return the count of fully filled bags.

1def maximumBags(capacity: list[int], rocks: list[int], additionalRocks: int) -> int:
2    remaining_space = sorted(c - r for c, r in zip(capacity, rocks))  # cheapest bags first
3    bags_filled = 0
4    for space in remaining_space:
5        if additionalRocks < space:
6            break  # can't fill this bag or any pricier one after it
7        additionalRocks -= space
8        bags_filled += 1
9    return bags_filled

Time: O(n log n) — the sort dominates; the single pass afterward is O(n).
Space: O(n) — for the remainingSpace array storing the computed gaps.

Complexity Summary

Common Mistakes

• Sorting in descending order — filling the bags that need the most rocks first burns your budget on the hardest cases and leaves easy bags unfilled; ascending order is the right choice.
• Missing the free bags — a bag where capacity[i] == rocks[i] has remaining space of 0 and gets filled without spending any rocks. Forgetting to count these understates the answer.
• Not breaking early — continuing to iterate after additionalRocks < space does not add to bagsFilled (the condition fails every time), but it wastes time and signals a misunderstanding of the sorted structure.
• Wrong difference direction — computing rocks[i] - capacity[i] instead of capacity[i] - rocks[i] produces negative values and breaks the sort; always think "how much space is left?"
• Greedy by original index or capacity — filling bags in input order, or by largest capacity, is not optimal; only sorting by remaining space guarantees you maximize the count.

Related Problems

• boats-to-save-people — sort by weight and use two pointers to greedily pair lightest with heaviest, same "sort then greedily consume" structure
• candy — greedy distribution of a resource (candy) under local ordering constraints, two-pass approach
• gas-station — greedy reasoning about whether a resource pool can sustain a complete circuit
• last-stone-weight — greedy resource elimination using a max-heap, different structure but same instinct of processing by value order
• partition-labels — greedy interval extension: commit to the cheapest completion of the current segment before moving on