Maximum Bags With Full Capacity of Rocks

Maximum Bags With Full Capacity of Rocks

What is this problem about?

You are given n bags. For each bag, you know its maximum capacity and the number of rocks currently inside it. You are also given an integer additionalRocks, representing extra rocks you can distribute among the bags however you want. Your objective is to place the extra rocks to maximize the number of bags that are completely full (where rocks == capacity).

Why is this asked in interviews?

This is a pure Greedy Algorithm problem with a sorting component. It acts as an excellent screening question. It tests whether a candidate can identify the bottleneck (the difference between capacity and current rocks) and realize that filling the bags that require the least amount of effort yields the highest count of full bags.

Algorithmic pattern used

This problem strictly relies on Sorting and Greedy Resource Allocation.

1. Calculate the "deficit" for every bag: deficit[i] = capacity[i] - rocks[i]. This is how many extra rocks the bag needs to become full.
2. Sort the deficit array in ascending order. (Bags that need 0 rocks are first, bags that need 1 rock are next, etc.).
3. Iterate through the sorted deficit array. If your additionalRocks is greater than or equal to the current deficit, subtract the deficit from your additionalRocks and increment your full_bags_count.
4. If you encounter a deficit you cannot afford, you can stop immediately, as all subsequent bags will require even more rocks.

Example explanation

Capacities: [2, 3, 4, 5], Current Rocks: [1, 2, 4, 4], Additional Rocks: 2.

1. Calculate deficits:
   • Bag 0: $2 - 1 = 1$
   • Bag 1: $3 - 2 = 1$
   • Bag 2: $4 - 4 = 0$
   • Bag 3: $5 - 4 = 1$ Deficits array: [1, 1, 0, 1].
2. Sort deficits: [0, 1, 1, 1].
3. Greedy allocation (Budget = 2):
   • Deficit 0: Costs 0. Budget = 2. Full bags = 1.
   • Deficit 1: Costs 1. Budget = 1. Full bags = 2.
   • Deficit 1: Costs 1. Budget = 0. Full bags = 3.
   • Deficit 1: Costs 1. Budget = 0. Cannot afford. Stop. Maximum full bags is 3.

Common mistakes candidates make

Candidates sometimes try to use a Priority Queue (Min-Heap) to solve this. While a Min-Heap conceptually works perfectly by popping the smallest deficit, inserting all elements into a heap takes $O(N \log N)$ and popping them takes $O(K \log N)$. Sorting the deficit array in-place takes $O(N \log N)$ but has much less overhead and simpler code. A more fundamental mistake is not sorting at all and trying to fill bags chronologically, which completely fails the greedy premise.

Interview preparation tip

For the Maximum Bags With Full Capacity coding problem, do not mutate the original capacity or rocks arrays. Create a brand new array int[] deficits. This isolates the only piece of data you actually care about (the difference). Sorting this single array keeps your logic mathematically pure and your code incredibly readable.