Maximum Bags With Full Capacity of Rocks

Med

#2077Time: O(2^n), where n is the number of bags. In the worst case, we explore every subset of the bags that are not initially full.Space: O(n), where n is the number of bags. This is for storing the `neededRocks` list and for the recursion stack depth in the worst case.

Patterns

Greedy

Algorithms

Sorting

Data structures

Array

Prompt

You have n bags numbered from 0 to n - 1. You are given two 0-indexed integer arrays capacity and rocks. The i^th 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 * 10⁴
1 <= capacity[i] <= 10⁹
0 <= rocks[i] <= capacity[i]
1 <= additionalRocks <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

This approach attempts to solve the problem by exploring every possible combination of bags to fill. It works by generating all subsets of bags that are not yet full. For each subset, it calculates the total number of additional rocks required to fill all bags within it. If this total is within our budget of additionalRocks, we compare the size of this subset to the maximum size found so far and update it if necessary. This guarantees finding the largest group of bags we can possibly fill, but at a very high computational cost.

Algorithm

Create a list, neededRocks, to store the rock requirement (capacity[i] - rocks[i]) for each bag that is not already full.
Implement a recursive function, say findMax(index, currentSum, currentCount), to explore all subsets of neededRocks.
The base cases for the recursion are:
- If currentSum exceeds additionalRocks, we cannot form this subset, so we return.
- We always update a global maximum count of bags with the currentCount.
- If index reaches the end of the neededRocks list, we have considered all possible bags for a subset, so we return.
In the recursive step, for each element at index, we make two calls:
- Include: Recurse with findMax(index + 1, currentSum + neededRocks[index], currentCount + 1).
- Exclude: Recurse with findMax(index + 1, currentSum, currentCount).
The initial call to the function would be findMax(0, 0, 0).
The final answer is the sum of the initially full bags and the maximum count found from the recursion.

Walkthrough

The core idea is to use recursion to build every possible subset of bags. We first filter out bags that are already at full capacity, as they don't require any of our additionalRocks. For the remaining bags, we calculate the number of rocks needed for each one. Then, a recursive helper function explores two possibilities for each bag: either we include it in our set of bags to fill (and subtract the required rocks from our budget), or we don't. By exploring all paths in this decision tree, we eventually check every single subset. We keep a global variable to track the size of the largest valid subset we've been able to form. While correct, this method is computationally infeasible for the given constraints.

1// Note: This code is for demonstration of the brute-force concept and will time out.2import java.util.ArrayList;3import java.util.List;4 5class Solution {6    int maxFilledFromSubset = 0;7 8    public int maximumBags(int[] capacity, int[] rocks, int additionalRocks) {9        int n = capacity.length;10        int initiallyFull = 0;11        List<Integer> needed = new ArrayList<>();12 13        for (int i = 0; i < n; i++) {14            if (capacity[i] == rocks[i]) {15                initiallyFull++;16            } else {17                needed.add(capacity[i] - rocks[i]);18            }19        }20 21        if (!needed.isEmpty()) {22            findMaxSubset(needed, 0, 0L, 0, additionalRocks);23        }24 25        return initiallyFull + maxFilledFromSubset;26    }27 28    private void findMaxSubset(List<Integer> needed, int index, long currentSum, int currentCount, int additionalRocks) {29        if (currentSum > additionalRocks) {30            return;31        }32 33        // Even if the sum is valid, we update the max count found so far.34        maxFilledFromSubset = Math.max(maxFilledFromSubset, currentCount);35 36        if (index == needed.size()) {37            return;38        }39 40        // Decision 1: Include the bag at the current index41        findMaxSubset(needed, index + 1, currentSum + needed.get(index), currentCount + 1, additionalRocks);42 43        // Decision 2: Exclude the bag at the current index44        findMaxSubset(needed, index + 1, currentSum, currentCount, additionalRocks);45    }46}

Complexity

Time

O(2^n), where n is the number of bags. In the worst case, we explore every subset of the bags that are not initially full.

Space

O(n), where n is the number of bags. This is for storing the `neededRocks` list and for the recursion stack depth in the worst case.

Trade-offs

Pros

It is a brute-force method that guarantees finding the correct answer by checking all possibilities.

Cons

Extremely inefficient due to its exponential time complexity.
Will result in a 'Time Limit Exceeded' error on any reasonably sized input.
The implementation is more complex than the optimal greedy approach.

A much more efficient solution uses a greedy strategy. The core intuition is that to maximize the number of bags we can fill, we should always prioritize filling the bags that are 'cheapest'—that is, those that require the fewest additional rocks. By satisfying the smallest requirements first, we make the most of our additionalRocks, increasing our chances of filling a larger quantity of bags. This approach avoids the exponential complexity of brute force by making a locally optimal choice at each step, which leads to a globally optimal solution.

Algorithm

Create an array, needed, of the same size as capacity.
Iterate through the bags from i = 0 to n-1. For each bag, calculate the number of rocks required to make it full: needed[i] = capacity[i] - rocks[i].
Sort the needed array in non-decreasing (ascending) order. This ensures that bags requiring fewer rocks are considered first.
Initialize a counter for the number of full bags, fullBags = 0.
Iterate through the sorted needed array. For each requirement in the array:
- Check if you have enough additionalRocks to meet the requirement.
- If additionalRocks >= requirement, you can fill this bag. Subtract the requirement from additionalRocks and increment fullBags.
- If additionalRocks < requirement, you cannot fill this bag. Since the array is sorted, you cannot fill any subsequent bags either, so you can break the loop.
Return the final fullBags count.

Walkthrough

This method begins by calculating the remaining capacity for every bag, which is capacity[i] - rocks[i]. These values represent the 'cost' to fill each bag. We store these costs in a new array.

Next, to apply the greedy strategy, we sort this array of costs in ascending order. This places the bags that are already full (cost 0) or nearly full (small cost) at the beginning.

Finally, we iterate through this sorted list of costs. We keep a running total of our available additionalRocks. For each bag's cost, we check if we can 'afford' it. If we do, we pay the cost by subtracting it from additionalRocks and increment a counter for filled bags. If we encounter a bag whose cost exceeds our remaining additionalRocks, we stop. Since the costs are sorted, we know we cannot afford to fill any of the remaining bags in the list. The final value of our counter is the maximum number of bags we can fill.

1import java.util.Arrays;2 3class Solution {4    public int maximumBags(int[] capacity, int[] rocks, int additionalRocks) {5        int n = capacity.length;6        int[] needed = new int[n];7 8        for (int i = 0; i < n; i++) {9            needed[i] = capacity[i] - rocks[i];10        }11 12        Arrays.sort(needed);13 14        int fullBags = 0;15        for (int i = 0; i < n; i++) {16            // If we can afford to fill this bag (even if it needs 0 rocks)17            if (additionalRocks >= needed[i]) {18                additionalRocks -= needed[i];19                fullBags++;20            } else {21                // Cannot afford this bag, nor any subsequent ones.22                break;23            }24        }25 26        return fullBags;27    }28}

Complexity

Time

O(n log n), where n is the number of bags. The calculation of needed rocks takes O(n), sorting takes O(n log n), and the final iteration takes O(n). The sorting step dominates the complexity.

Space

O(n) or O(log n). O(n) to store the `needed` array. The sort algorithm itself (`Arrays.sort` for primitives in Java) uses O(log n) space for the call stack. If we are allowed to modify an input array, space could be reduced to O(log n).

Trade-offs

Pros

Highly efficient with a time complexity of O(n log n).
Guaranteed to find the optimal solution.
Simple to understand and implement.

Cons

Requires extra space to store the needed array. This can be O(n).
The time complexity is bound by sorting, so it's not a linear time solution.

Solutions

Solution

1class Solution { public int maximumBags ( int [] capacity , int [] rocks , int additionalRocks ) { int n = capacity . length ; int [] d = new int [ n ]; for ( int i = 0 ; i < n ; ++ i ) { d [ i ] = capacity [ i ] - rocks [ i ]; } Arrays . sort ( d ); int ans = 0 ; for ( int v : d ) { if ( v <= additionalRocks ) { ++ ans ; additionalRocks -= v ; } else { break ; } } return ans ; } }

1class Solution { public: int maximumBags ( vector < int >& capacity , vector < int >& rocks , int additionalRocks ) { int n = capacity . size (); vector < int > d ( n ); for ( int i = 0 ; i < n ; ++ i ) d [ i ] = capacity [ i ] - rocks [ i ]; sort ( d . begin (), d . end ()); int ans = 0 ; for ( int & v : d ) { if ( v > additionalRocks ) break ; ++ ans ; additionalRocks -= v ; } return ans ; } };

1class Solution : def maximumBags ( self , capacity : List [ int ], rocks : List [ int ], additionalRocks : int ) -> int : d = [ a - b for a , b in zip ( capacity , rocks )] d . sort () ans = 0 for v in d : if v <= additionalRocks : ans += 1 additionalRocks -= v return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem