Problem Description

You are given n bags numbered from 0 to n - 1. Each bag has a certain capacity and currently contains some rocks.

You have:

• An array capacity where capacity[i] represents the maximum number of rocks that bag i can hold
• An array rocks where rocks[i] represents the current number of rocks in bag i
• An integer additionalRocks representing extra rocks you can distribute among the bags

Your goal is to maximize the number of bags that are completely full (where the number of rocks equals the bag's capacity) by strategically placing the additional rocks.

For example, if you have:

• capacity = [2, 3, 4, 5]
• rocks = [1, 2, 4, 4]
• additionalRocks = 2

The bags need [1, 1, 0, 1] more rocks to be full. With 2 additional rocks, you can fill the first two bags (needing 1 rock each), resulting in 3 full bags total.

The solution works by:

1. Calculating how many more rocks each bag needs to be full (capacity[i] - rocks[i])
2. Sorting these remaining capacities in ascending order
3. Greedily filling bags that need the fewest additional rocks first
4. Counting how many bags can be completely filled with the available additional rocks

The function returns the maximum number of bags that can reach full capacity.

Intuition

The key insight is that we want to maximize the count of full bags, not the total number of rocks placed. This means we should prioritize filling bags that are already close to being full.

Think of it this way: if you have 5 additional rocks and two bags - one needs 5 rocks to be full and another needs just 1 rock - it's better to fill the second bag completely (using 1 rock) than to put all 5 rocks in the first bag. This gives us 1 full bag instead of 0.

This naturally leads to a greedy strategy: always fill the bags that need the fewest additional rocks first. By doing this, we can fill more bags with our limited supply of additional rocks.

Why does this greedy approach work? Because:

1. Each full bag contributes exactly 1 to our answer, regardless of its capacity
2. We have a fixed number of additional rocks to distribute
3. To maximize the number of full bags, we should "spend" our additional rocks as efficiently as possible

The remaining capacity of each bag (capacity[i] - rocks[i]) tells us exactly how many rocks we need to make that bag full. By sorting these values and filling bags in ascending order of their remaining capacity, we ensure that we fill the maximum possible number of bags before running out of additional rocks.

This is similar to buying items with limited money - if you want to buy as many items as possible, you'd start with the cheapest ones first.

Learn more about Greedy and Sorting patterns.

Solution Approach

The implementation follows a simple sorting and greedy approach:

Step 1: Calculate remaining capacities
First, we transform the problem by calculating how many more rocks each bag needs to be full. We reuse the capacity array to store these values:

for i, x in enumerate(rocks):
    capacity[i] -= x

After this step, capacity[i] now represents the number of additional rocks needed to fill bag i.

Step 2: Sort the remaining capacities
We sort the array in ascending order:

capacity.sort()

This ensures we process bags that need fewer rocks first, implementing our greedy strategy.

Step 3: Fill bags greedily
We iterate through the sorted array and try to fill each bag:

for i, x in enumerate(capacity):
    additionalRocks -= x
    if additionalRocks < 0:
        return i

For each bag:

• We subtract the rocks needed (x) from our available additionalRocks
• If additionalRocks becomes negative, it means we couldn't fully fill this bag, so we return i (the number of bags we successfully filled before this one)
• If we can fill the bag, we continue to the next one

Step 4: Return the result
If we successfully process all bags without running out of additional rocks, we return the total number of bags:

return len(capacity)

Time Complexity: O(n log n) due to sorting
Space Complexity: O(1) as we reuse the input array for storing remaining capacities

The algorithm is efficient because it makes optimal local choices (filling the easiest bags first) that lead to the globally optimal solution (maximum number of full bags).

Example Walkthrough

Let's walk through a concrete example to see how the solution works:

Given:

• capacity = [10, 2, 2] (maximum rocks each bag can hold)
• rocks = [5, 2, 1] (current rocks in each bag)
• additionalRocks = 100 (rocks we can distribute)

Step 1: Calculate remaining capacities

We compute how many more rocks each bag needs:

• Bag 0: needs 10 - 5 = 5 rocks
• Bag 1: needs 2 - 2 = 0 rocks (already full!)
• Bag 2: needs 2 - 1 = 1 rock

So our remaining capacities array becomes: [5, 0, 1]

Step 2: Sort the remaining capacities

After sorting in ascending order: [0, 1, 5]

This represents the bags ordered by how many rocks they need:

• First bag needs 0 rocks (already full)
• Second bag needs 1 rock
• Third bag needs 5 rocks

Step 3: Fill bags greedily

We iterate through the sorted array and try to fill each bag:

• Iteration 1: Need 0 rocks, additionalRocks = 100 - 0 = 100. We can fill this bag! Count = 1
• Iteration 2: Need 1 rock, additionalRocks = 100 - 1 = 99. We can fill this bag! Count = 2
• Iteration 3: Need 5 rocks, additionalRocks = 99 - 5 = 94. We can fill this bag! Count = 3

Step 4: Return the result

Since we successfully filled all bags and still have 94 rocks left over, we return 3.

Key Insight: By sorting and filling bags that need fewer rocks first, we maximized the number of full bags. If we had started with the bag needing 5 rocks, we would still end up with 3 full bags, but the greedy approach ensures we always get the maximum possible count even with limited resources.

Solution Implementation

Time and Space Complexity

The time complexity is O(n × log n), where n is the number of bags. This is dominated by the sorting operation capacity.sort(), which uses Python's Timsort algorithm with O(n × log n) complexity. The two linear loops (one for calculating remaining capacity and one for distributing additional rocks) each take O(n) time, but these are overshadowed by the sorting step.

The space complexity is O(log n). While the algorithm modifies the capacity list in-place without creating additional data structures of size n, Python's sorting algorithm (Timsort) requires O(log n) space for its recursive call stack during the sorting process. This is the primary space overhead beyond the input arrays themselves.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Modifying Input Arrays Without Consideration

A common pitfall is directly modifying the input capacity array to store remaining capacities, which can cause issues if the original values are needed later or if the function is expected to be pure (not modifying inputs).

Problem Code:

for i, x in enumerate(rocks):
    capacity[i] -= x  # Directly modifying input array
capacity.sort()

Solution: Create a new array to store the remaining capacities instead of modifying the input:

remaining_capacity = [capacity[i] - rocks[i] for i in range(len(capacity))]
remaining_capacity.sort()

2. Integer Overflow in Subtraction

When subtracting additionalRocks -= space_needed, if not careful with the logic, you might continue processing even after additionalRocks becomes negative, leading to incorrect results.

Problem Code:

for space_needed in remaining_capacity:
    additionalRocks -= space_needed  # Always subtracting
    if additionalRocks >= 0:
        full_bags_count += 1

Solution: Check before subtracting to avoid unnecessary operations and potential confusion:

for space_needed in remaining_capacity:
    if additionalRocks >= space_needed:
        additionalRocks -= space_needed
        full_bags_count += 1
    else:
        break  # No point continuing

3. Not Handling Edge Cases

Failing to consider edge cases like empty arrays or when all bags are already full.

Problem Scenario:

• What if capacity and rocks are empty arrays?
• What if all bags are already full (all capacity[i] == rocks[i])?

Solution: Add validation at the beginning:

if not capacity:  # Empty input
    return 0

remaining_capacity = [capacity[i] - rocks[i] for i in range(len(capacity))]
# Filter out already full bags (where remaining_capacity is 0)
remaining_capacity = [x for x in remaining_capacity if x > 0]

4. Inefficient Space Usage

Creating multiple intermediate arrays unnecessarily when the problem can be solved more efficiently.

Problem Code:

remaining = []
for i in range(len(capacity)):
    remaining.append(capacity[i] - rocks[i])
sorted_remaining = sorted(remaining)  # Creates another array

Solution: Use more concise and efficient approaches:

# One-liner list comprehension and sort in-place
remaining_capacity = [c - r for c, r in zip(capacity, rocks)]
remaining_capacity.sort()