{x}
blog image

Maximum Bags With Full Capacity of Rocks

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.

 

Example 1:

Input: capacity = [2,3,4,5], rocks = [1,2,4,4], additionalRocks = 2
Output: 3
Explanation:
Place 1 rock in bag 0 and 1 rock in bag 1.
The number of rocks in each bag are now [2,3,4,4].
Bags 0, 1, and 2 have full capacity.
There are 3 bags at full capacity, so we return 3.
It can be shown that it is not possible to have more than 3 bags at full capacity.
Note that there may be other ways of placing the rocks that result in an answer of 3.

Example 2:

Input: capacity = [10,2,2], rocks = [2,2,0], additionalRocks = 100
Output: 3
Explanation:
Place 8 rocks in bag 0 and 2 rocks in bag 2.
The number of rocks in each bag are now [10,2,2].
Bags 0, 1, and 2 have full capacity.
There are 3 bags at full capacity, so we return 3.
It can be shown that it is not possible to have more than 3 bags at full capacity.
Note that we did not use all of the additional rocks.

 

Constraints:

  • n == capacity.length == rocks.length
  • 1 <= n <= 5 * 104
  • 1 <= capacity[i] <= 109
  • 0 <= rocks[i] <= capacity[i]
  • 1 <= additionalRocks <= 109

Solution Explanation: Maximum Bags With Full Capacity of Rocks

This problem asks to find the maximum number of bags that can be filled to their capacity given a limited number of additional rocks. The optimal approach leverages a greedy strategy combined with sorting.

Approach:

  1. Calculate Remaining Capacity: For each bag, determine the number of additional rocks needed to fill it completely. This is simply the difference between the bag's capacity and its current number of rocks.

  2. Sort Remaining Capacities: Sort the calculated remaining capacities in ascending order. This ensures we prioritize filling the bags requiring the fewest additional rocks first.

  3. Greedy Filling: Iterate through the sorted remaining capacities. For each bag:

    • If we have enough additionalRocks to fill the bag, subtract the required rocks from additionalRocks and increment the count of filled bags.
    • If we don't have enough additionalRocks, we can't fill any more bags, so we return the current count of filled bags.

  4. Return Filled Bag Count: If we've gone through all bags without running out of additionalRocks, all bags are filled, and we return the total number of bags.

Time and Space Complexity:

  • Time Complexity: O(n log n), dominated by the sorting step. The remaining operations (calculating differences, iterating) are linear, O(n).
  • Space Complexity: O(log n) or O(n) depending on the sorting algorithm used. In-place sorting algorithms like quicksort or heapsort would have O(log n) auxiliary space, while merge sort uses O(n) space. We also need O(1) extra space for variables.

Code Implementation (Python):

class Solution:
    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:
        remaining_capacities = [c - r for c, r in zip(capacity, rocks)]  #Step 1
        remaining_capacities.sort() #Step 2
        filled_bags = 0
        for remaining in remaining_capacities: #Step 3
            if additionalRocks >= remaining:
                additionalRocks -= remaining
                filled_bags += 1
            else:
                break  # Not enough rocks left
        return filled_bags #Step 4

Code Implementation (Java):

import java.util.Arrays;
 
class Solution {
    public int maximumBags(int[] capacity, int[] rocks, int additionalRocks) {
        int n = capacity.length;
        int[] remaining = new int[n];
        for (int i = 0; i < n; i++) {
            remaining[i] = capacity[i] - rocks[i];
        }
        Arrays.sort(remaining); //Step 2
        int filledBags = 0;
        for (int rem : remaining) { //Step 3
            if (additionalRocks >= rem) {
                additionalRocks -= rem;
                filledBags++;
            } else {
                break;
            }
        }
        return filledBags; //Step 4
    }
}

The other language implementations (C++, Go, TypeScript, Rust) follow a very similar structure, differing only in syntax. The core algorithm remains consistent across all languages.