# Maximum Bags With Full Capacity of Rocks
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-bags-with-full-capacity-of-rocks)
Canonical: https://scaleengineer.com/dsa/problems/maximum-bags-with-full-capacity-of-rocks
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
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`

# Approaches
## Brute Force by Checking All Subsets
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.
**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.
**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.
### Explanation
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.

```java
// Note: This code is for demonstration of the brute-force concept and will time out.
import java.util.ArrayList;
import java.util.List;

class Solution {
    int maxFilledFromSubset = 0;

    public int maximumBags(int[] capacity, int[] rocks, int additionalRocks) {
        int n = capacity.length;
        int initiallyFull = 0;
        List<Integer> needed = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            if (capacity[i] == rocks[i]) {
                initiallyFull++;
            } else {
                needed.add(capacity[i] - rocks[i]);
            }
        }

        if (!needed.isEmpty()) {
            findMaxSubset(needed, 0, 0L, 0, additionalRocks);
        }

        return initiallyFull + maxFilledFromSubset;
    }

    private void findMaxSubset(List<Integer> needed, int index, long currentSum, int currentCount, int additionalRocks) {
        if (currentSum > additionalRocks) {
            return;
        }

        // Even if the sum is valid, we update the max count found so far.
        maxFilledFromSubset = Math.max(maxFilledFromSubset, currentCount);

        if (index == needed.size()) {
            return;
        }

        // Decision 1: Include the bag at the current index
        findMaxSubset(needed, index + 1, currentSum + needed.get(index), currentCount + 1, additionalRocks);

        // Decision 2: Exclude the bag at the current index
        findMaxSubset(needed, index + 1, currentSum, currentCount, additionalRocks);
    }
}
```
### Algorithm
1. Create a list, `neededRocks`, to store the rock requirement (`capacity[i] - rocks[i]`) for each bag that is not already full.
2. Implement a recursive function, say `findMax(index, currentSum, currentCount)`, to explore all subsets of `neededRocks`.
3. 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.
4. 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)`.
5. The initial call to the function would be `findMax(0, 0, 0)`.
6. The final answer is the sum of the initially full bags and the maximum count found from the recursion.

## Greedy Approach with Sorting
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.
**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).
**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.
### Explanation
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.

```java
import java.util.Arrays;

class Solution {
    public int maximumBags(int[] capacity, int[] rocks, int additionalRocks) {
        int n = capacity.length;
        int[] needed = new int[n];

        for (int i = 0; i < n; i++) {
            needed[i] = capacity[i] - rocks[i];
        }

        Arrays.sort(needed);

        int fullBags = 0;
        for (int i = 0; i < n; i++) {
            // If we can afford to fill this bag (even if it needs 0 rocks)
            if (additionalRocks >= needed[i]) {
                additionalRocks -= needed[i];
                fullBags++;
            } else {
                // Cannot afford this bag, nor any subsequent ones.
                break;
            }
        }

        return fullBags;
    }
}
```
### Algorithm
1. Create an array, `needed`, of the same size as `capacity`.
2. 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]`.
3. Sort the `needed` array in non-decreasing (ascending) order. This ensures that bags requiring fewer rocks are considered first.
4. Initialize a counter for the number of full bags, `fullBags = 0`.
5. 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.
6. Return the final `fullBags` count.

# Solutions
### Java

```java
class 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 ; } }
```

### CPP

```cpp
class 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 ; } };
```

### Python

```python
class 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
```