LeetCode 2279 - Maximum Bags With Full Capacity of Rocks

The problem presents n bags, each with a defined maximum capacity and a current number of rocks. The input consists of two arrays: capacity and rocks, where capacity[i] is the maximum number of rocks bag i can hold, and rocks[i] is how many rocks are currently in that bag.

leetcodemediumarraygreedysorting

LeetCode Problem 2279

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting

Solution

Problem Understanding

The problem presents n bags, each with a defined maximum capacity and a current number of rocks. The input consists of two arrays: capacity and rocks, where capacity[i] is the maximum number of rocks bag i can hold, and rocks[i] is how many rocks are currently in that bag. Additionally, you are given an integer additionalRocks, representing rocks you can distribute freely among any of the bags.

The goal is to maximize the number of bags that reach full capacity after distributing these additional rocks. The output is a single integer, representing this maximum number of full bags.

The constraints indicate potentially large inputs (n up to 50,000 and rock quantities up to 10^9), which rules out brute-force enumeration over all distributions. The problem guarantees that each rocks[i] is less than or equal to capacity[i], so no bag is overfilled initially.

Key edge cases include bags that are already full, bags that require exactly one rock to fill, and situations where the number of additionalRocks exceeds the sum of all deficits or is zero.

Approaches

A brute-force approach would involve trying all combinations of distributing additionalRocks among the bags and checking which combination maximizes the number of full bags. While correct in principle, this is computationally infeasible because the number of possible distributions grows combinatorially with n and additionalRocks.

The key observation for an optimal approach is that the order of filling bags matters, and to maximize full bags, it is best to fill the bags that need the fewest rocks first. This insight leads to a greedy solution: compute the number of rocks needed to fill each bag (capacity[i] - rocks[i]), sort these values in ascending order, and then use the additional rocks starting from the smallest requirement until they are exhausted.

Approach Time Complexity Space Complexity Notes
Brute Force O( (additionalRocks + n)! / (additionalRocks! * n!) ) O(n) Tries all distributions of additional rocks
Optimal (Greedy + Sorting) O(n log n) O(n) Sort deficits and fill bags greedily from smallest deficit

Algorithm Walkthrough

  1. Compute the deficit for each bag, defined as the number of rocks required to reach full capacity: deficit[i] = capacity[i] - rocks[i].
  2. Sort the deficit array in ascending order. This allows us to prioritize filling bags that require fewer rocks first.
  3. Initialize a counter fullBags to zero. This will track the number of bags that reach full capacity.
  4. Iterate through the sorted deficit array. For each deficit d, check if the remaining additionalRocks is greater than or equal to d. If yes, subtract d from additionalRocks and increment fullBags. If not, break the loop as no further bag can be filled.
  5. Return fullBags as the maximum number of full bags.

Why it works: By always filling the bags that require the fewest rocks first, the algorithm maximizes the number of bags that reach capacity with the limited additional rocks. Any other order would either leave smaller deficits unfilled or waste rocks on bags that require more than necessary.

Python Solution

from typing import List

class Solution:
    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:
        deficits = [capacity[i] - rocks[i] for i in range(len(capacity))]
        deficits.sort()
        fullBags = 0
        
        for d in deficits:
            if additionalRocks >= d:
                additionalRocks -= d
                fullBags += 1
            else:
                break
        
        return fullBags

The code first computes the deficits for all bags and sorts them to prioritize the smallest. Then it iterates through these deficits, using additionalRocks to fill as many bags as possible. The moment there are insufficient rocks to fill the next bag, the loop stops, and the result is returned.

Go Solution

import "sort"

func maximumBags(capacity []int, rocks []int, additionalRocks int) int {
    n := len(capacity)
    deficits := make([]int, n)
    for i := 0; i < n; i++ {
        deficits[i] = capacity[i] - rocks[i]
    }
    
    sort.Ints(deficits)
    fullBags := 0
    
    for _, d := range deficits {
        if additionalRocks >= d {
            additionalRocks -= d
            fullBags++
        } else {
            break
        }
    }
    
    return fullBags
}

The Go implementation mirrors the Python logic. The primary differences are explicit slice allocation for deficits and using sort.Ints for sorting. The iteration uses Go’s range construct, but the greedy logic is identical.

Worked Examples

Example 1:

capacity = [2,3,4,5], rocks = [1,2,4,4], additionalRocks = 2
deficits = [1,1,0,1]
sorted deficits = [0,1,1,1]

Stepwise:

Deficit Additional Rocks Action Full Bags
0 2 fill 1
1 2-1=1 fill 2
1 1-1=0 fill 3
1 0 cannot fill 3

Output: 3

Example 2:

capacity = [10,2,2], rocks = [2,2,0], additionalRocks = 100
deficits = [8,0,2]
sorted deficits = [0,2,8]

Stepwise:

Deficit Additional Rocks Action Full Bags
0 100 fill 1
2 100-2=98 fill 2
8 98-8=90 fill 3

Output: 3

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting the deficits array dominates the computation.
Space O(n) Extra array for deficits of each bag.

The time complexity is driven by the sorting step. Iterating through the array is linear, and the space complexity is linear due to storing the deficits.

Test Cases

# Provided examples
assert Solution().maximumBags([2,3,4,5], [1,2,4,4], 2) == 3  # Example 1
assert Solution().maximumBags([10,2,2], [2,2,0], 100) == 3  # Example 2

# Edge cases
assert Solution().maximumBags([1], [0], 1) == 1  # Single bag, exactly enough rocks
assert Solution().maximumBags([1], [0], 0) == 0  # Single bag, no additional rocks
assert Solution().maximumBags([5,5,5], [5,5,5], 10) == 3  # All bags already full
assert Solution().maximumBags([3,3,3], [0,0,0], 2) == 0  # Not enough rocks to fill any bag
assert Solution().maximumBags([3,3,3], [0,0,0], 3) == 1  # Exactly enough for one bag
assert Solution().maximumBags([1,2,3], [0,0,0], 6) == 3  # Enough to fill all bags
Test Why
Single bag with rocks Validates minimum input size
No additional rocks Ensures algorithm handles zero extra rocks
All bags already full Confirms algorithm does not overfill
Insufficient rocks Checks correct stopping when rocks run out
Exactly enough rocks for one Validates proper allocation
Enough rocks for all Confirms algorithm fills all possible bags

Edge Cases

The first edge case is when a bag is already full. The algorithm handles this by computing deficits; a deficit of zero is sorted first and counted immediately as a full bag without using any additional rocks.

The second edge case is when additionalRocks exceeds the sum of all deficits. The loop will fill every bag with a deficit, leaving unused rocks, which does not affect the correctness.

The third edge case is when additionalRocks is zero. The algorithm correctly counts only bags that already have zero deficit as full, ignoring bags that need rocks, and terminates immediately once it encounters a non-zero deficit.

This approach handles these scenarios seamlessly due to its greedy and sorted deficit methodology.