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:
-
Calculate the difference between the
capacity
and therocks
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 thecapacity
array andb
represents the corresponding element from therocks
array. Thezip
function pairs each element fromcapacity
with the corresponding element fromrocks
. -
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()
-
Initialize a variable
ans
to count the number of bags that can be filled to full capacity:1ans = 0
-
Iterate through the sorted list
d
and try to fill each bag. If theadditionalRocks
is enough to fill the current bag, increase theans
by 1 and reduceadditionalRocks
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 leastv
, it means we can fill this bag. Then we updateadditionalRocks
to reflect the rocks used. - The loop continues either until there are no more rocks left (
additionalRocks
is less than the nextv
in the list) or all bags are checked.
-
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
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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:
-
First, we calculate the difference between
capacity
androcks
for each bag.Using the list comprehension:
1d = [a - b for a, b in zip(capacity, rocks)] # d will become [1, 1, 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]
-
We initialize
ans
to keep track of the bags that can be filled to full capacity:1ans = 0 # Starts at 0
-
Now, we iterate through the sorted list
d
and distributeadditionalRocks
: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, soans
becomes1
andadditionalRocks
becomes2
.The second bag also needs
1
rock, soans
is incremented to2
andadditionalRocks
is reduced to1
.The third bag needs
2
rocks to be full. However, we only have1
additionalRock
left, so we cannot fill this bag to capacity. -
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.
Solution Implementation
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
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
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
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:
- The list comprehension
d = [a - b for a, b in zip(capacity, rocks)]
takesO(n)
time, wheren
is the number of elements incapacity
androcks
. - Sorting the list
d.sort()
has a time complexity ofO(n log n)
because it uses the Timsort algorithm which is Python's standard sorting algorithm. - The loop
for v in d:
iterates through each element of the listd
once, giving a time complexity ofO(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:
- The list comprehension generates a new list
d
of sizen
, resulting inO(n)
space complexity. - Sorting the list is done in-place in Python, so it doesn't require additional space other than some constant workspace, hence
O(1)
. - The variables
ans
andadditionalRocks
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.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following array represent a max heap?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.