2279. Maximum Bags With Full Capacity of Rocks


Problem Description

In this problem, we're dealing with a set of n bags, each with a certain capacity. The capacity array represents the maximum number of rocks each bag can hold, while the rocks array shows the current number of rocks in each bag. We also have a certain number of additionalRocks that we can distribute across these bags.

The objective is to maximize the number of bags that are filled to their full capacity using the additionalRocks available. A bag is considered to be at full capacity if the number of rocks it contains equals its capacity.

Intuition

The intuition behind the solution is based on the idea that to maximize the number of bags at full capacity, we should fill the bags that need the fewest additional rocks first. This is a greedy approach where we prioritize the bags that are closest to being full because adding rocks to them will quickly increase the count of fully filled bags.

We calculate the difference between the capacity and rocks for each bag, which represents the number of additional rocks needed to fill each bag to capacity. We then sort this list to get the bags that need the least additional rocks at the beginning.

Stepping through this sorted list, we distribute the additionalRocks as long as we have enough to fill a bag. Each time we fill a bag, we decrement the number of additionalRocks by the number used and increment the count of fully-filled bags by one. This process continues until we run out of additionalRocks or fill all the bags. The final count of fully-filled bags is the maximum number we can achieve with the given additionalRocks.

Solution Approach

The solution implements a simple greedy strategy using Python lists and sorting algorithm. Here's a step-by-step walkthrough of the implementation:

  1. Calculate the difference between the capacity and the rocks for each bag to find out how many more rocks are needed to reach full capacity. This is done using a list comprehension:

    1d = [a - b for a, b in zip(capacity, rocks)]

    Here, a represents an element from the capacity array and b represents the corresponding element from the rocks array. The zip function pairs each element from capacity with the corresponding element from rocks.

  2. The problem is now reduced to filling the bags with the least difference first. To do this efficiently, sort the list d in non-decreasing order:

    1d.sort()
  3. Initialize a variable ans to count the number of bags that can be filled to full capacity:

    1ans = 0
  4. Iterate through the sorted list d and try to fill each bag. If the additionalRocks is enough to fill the current bag, increase the ans by 1 and reduce additionalRocks by the amount used:

    1for v in d:
    2    if v <= additionalRocks:
    3        ans += 1
    4        additionalRocks -= v
    • v represents the number of additional rocks needed for the current bag.
    • If additionalRocks is at least v, it means we can fill this bag. Then we update additionalRocks to reflect the rocks used.
    • The loop continues either until there are no more rocks left (additionalRocks is less than the next v in the list) or all bags are checked.
  5. Once the loop is complete, ans is the maximum number of bags that can be filled to full capacity, and the function returns this value:

    1return ans

This approach uses the built-in sorting function which typically has a time complexity of O(n log n) where n is the number of elements in the list. The subsequent iteration through the sorted list has a linear time complexity of O(n). As a result, the overall time complexity of this approach is O(n log n). The space complexity is O(n) due to the creation of the list d.

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose we have the following inputs:

  • capacity array: [5, 3, 7]
  • rocks array: [4, 2, 5]
  • additionalRocks: 3

We want to find out the maximum number of bags that can be filled to their full capacity using these 3 additional rocks.

Following the steps outlined in the solution approach:

  1. First, we calculate the difference between capacity and rocks for each bag.

    Using the list comprehension:

    1d = [a - b for a, b in zip(capacity, rocks)]  # d will become [1, 1, 2]
  2. We then sort this list to consider the bags that need the fewest additional rocks first:

    1d.sort()  # The sorted list d will remain [1, 1, 2]
  3. We initialize ans to keep track of the bags that can be filled to full capacity:

    1ans = 0  # Starts at 0
  4. Now, we iterate through the sorted list d and distribute additionalRocks:

    1# Loop through [1, 1, 2] with additionalRocks starting at 3
    2for v in d:
    3    if v <= additionalRocks:
    4        ans += 1            # Increment the count of full bags
    5        additionalRocks -= v  # Decrease the additionalRocks by v

    The first bag needs 1 rock to be full, which we have, so ans becomes 1 and additionalRocks becomes 2.

    The second bag also needs 1 rock, so ans is incremented to 2 and additionalRocks is reduced to 1.

    The third bag needs 2 rocks to be full. However, we only have 1 additionalRock left, so we cannot fill this bag to capacity.

  5. The process stops here as we have distributed all additional rocks that we can. The final count of fully-filled bags is the value of ans:

    1return ans  # Returns 2 as the maximum number of full bags

Therefore, we have maximized the number of full bags (2 out of 3) using the 3 additionalRocks provided.

Python Solution

1from typing import List
2
3class Solution:
4    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:
5        # Calculate the remaining capacity of each bag by subtracting the number of rocks
6        # currently in each bag from the bag's total capacity.
7        remaining_capacity = [total_cap - current_rocks for total_cap, current_rocks in zip(capacity, rocks)]
8      
9        # Sort the remaining capacities to prioritize bags that need fewer rocks to reach capacity
10        remaining_capacity.sort()
11      
12        # Initialize the counter for the number of bags that can be completely filled
13        filled_bags = 0
14      
15        # Iterate through the sorted remaining capacities
16        for required_rocks in remaining_capacity:
17          
18            # If the current bag requires fewer or equal rocks than we have available,
19            # use those rocks to fill the bag
20            if required_rocks <= additionalRocks:
21              
22                # Increment the filled bags counter
23                filled_bags += 1
24              
25                # Decrement the available rocks by the number of rocks used for the current bag
26                additionalRocks -= required_rocks
27            else:
28                # If the current bag requires more rocks than available, break the loop,
29                # as no further bags can be completely filled
30                break
31
32        # Return the total number of completely filled bags
33        return filled_bags
34

Java Solution

1class Solution {
2
3    // Function to determine the maximum number of bags that can be filled given capacities, current rocks, and additional rocks.
4    public int maximumBags(int[] capacity, int[] rocks, int additionalRocks) {
5        // Get the number of bags by checking the length of the capacity array.
6        int numBags = capacity.length;
7      
8        // Create an array to store the difference between capacity and current rocks in each bag.
9        int[] remainingCapacity = new int[numBags];
10      
11        // Calculate the remaining capacity for each bag.
12        for (int i = 0; i < numBags; ++i) {
13            remainingCapacity[i] = capacity[i] - rocks[i];
14        }
15      
16        // Sort the remaining capacities in ascending order; to fill as many bags as possible starting with the ones requiring the least additional rocks.
17        Arrays.sort(remainingCapacity);
18      
19        // Initialize a counter for the maximum number of bags that can be filled.
20        int maxFilledBags = 0;
21      
22        // Iterate over the sorted remaining capacities.
23        for (int requiredRocks : remainingCapacity) {
24            // If the required rocks to fill a bag is less than or equal to the available additional rocks...
25            if (requiredRocks <= additionalRocks) {
26                // Increment the count of filled bags.
27                maxFilledBags++;
28              
29                // Subtract the used rocks from the available additional rocks.
30                additionalRocks -= requiredRocks;
31            } else {
32                // If the remaining rocks are not sufficient to fill the next bag, break out of the loop.
33                break;
34            }
35        }
36      
37        // Return the maximum number of bags that can be filled.
38        return maxFilledBags;
39    }
40}
41

C++ Solution

1class Solution {
2public:
3    // Function to find the maximum number of bags that can be filled given the remaining capacity.
4    int maximumBags(vector<int>& capacity, vector<int>& rocks, int additionalRocks) {
5        int numBags = capacity.size(); // Get the number of bags.
6        vector<int> remainingCapacity(numBags); // Vector to hold remaining capacities of the bags.
7
8        // Calculate the remaining capacity for each bag.
9        for (int i = 0; i < numBags; ++i) {
10            remainingCapacity[i] = capacity[i] - rocks[i];
11        }
12
13        // Sort the remaining capacities in ascending order.
14        sort(remainingCapacity.begin(), remainingCapacity.end());
15
16        int maxFilledBags = 0; // Counter for maximum number of bags that can be completely filled.
17
18        // Iterate over each bag's remaining capacity.
19        for (int& remaining : remainingCapacity) {
20            // If there are not enough rocks to fill the next bag, break the loop.
21            if (remaining > additionalRocks) break;
22
23            // If we have enough rocks to fill the current bag:
24            maxFilledBags++;                  // Increment the count of filled bags.
25            additionalRocks -= remaining;     // Use the rocks to fill the bag.
26        }
27
28        return maxFilledBags; // Return the maximum number of bags that can be filled.
29    }
30};
31

Typescript Solution

1// Function to determine the maximum number of bags that can be filled to capacity
2// with a given number of additional rocks.
3// 'capacity' array represents the capacity of each bag.
4// 'rocks' array represents the current number of rocks in each bag.
5// 'additionalRocks' represents the total number of additional rocks available.
6function maximumBags(capacity: number[], rocks: number[], additionalRocks: number): number {
7    // Get the number of bags
8    const numBags = capacity.length;
9  
10    // Calculate the difference between bag capacity and current number of rocks
11    const requiredRocks = capacity.map((cap, index) => cap - rocks[index]);
12
13    // Sort the required rocks in ascending order - to prioritize bags that need fewer rocks to reach capacity
14    requiredRocks.sort((a, b) => a - b);
15  
16    // Initialize a counter to keep track of the number of bags that can be filled
17    let filledBags = 0;
18  
19    // Iterate over the sorted bags and try to fill them
20    for (let i = 0; i < numBags && (requiredRocks[i] === 0 || requiredRocks[i] <= additionalRocks); i++) {
21        filledBags++; // Increment filled bags count
22        additionalRocks -= requiredRocks[i]; // Subtract the used rocks from the additional rocks
23    }
24  
25    // Return the number of bags that have been filled to capacity
26    return filledBags;
27}
28

Time and Space Complexity

Time Complexity

The time complexity of the provided code consists of several parts:

  1. The list comprehension d = [a - b for a, b in zip(capacity, rocks)] takes O(n) time, where n is the number of elements in capacity and rocks.
  2. Sorting the list d.sort() has a time complexity of O(n log n) because it uses the Timsort algorithm which is Python's standard sorting algorithm.
  3. The loop for v in d: iterates through each element of the list d once, giving a time complexity of O(n).

Since sorting the list is the most expensive operation, the overall time complexity of the code is O(n log n).

Space Complexity

The space complexity of the code also involves a few components:

  1. The list comprehension generates a new list d of size n, resulting in O(n) space complexity.
  2. Sorting the list is done in-place in Python, so it doesn't require additional space other than some constant workspace, hence O(1).
  3. The variables ans and additionalRocks use constant space, O(1).

Combining these, the total space complexity of the code is O(n) because the new list d is the dominant factor.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫