2279. Maximum Bags With Full Capacity of Rocks

Hello, reader 👋🏽 ! Welcome to day 87 of the series on Problem Solving. Through this series, I aim to pick up at least one question every day and share my approach to solving it.

Today, I will be picking up LeetCode's daily challenge problem: 2279. Maximum Bags With Full Capacity of Rocks.

🤔 Problem Statement

You have n bags numbered from 0 to n - 1.
You are given two 0-indexed integer arrays capacity and rocks.
The i<sup>th</sup> 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.
E.g.:
- capacity = [2,3,4,5], rocks = [1,2,4,4], additionalRocks = 2 => 3
- capacity = [10,2,2], rocks = [2,2,0], additionalRocks = 100 => 3

💬 Thought Process - Greedy

This is a classic greedy problem where we have to return the maximum number of bags that could have full capacity.
If you think carefully, you can have the maximum number of bags to full capacity by first filling the bags that have lesser capacity than those that have a larger capacity.
Let's understand with this example:
- capacity = [2,3,4,5], rocks = [1,2,4,4], additionalRocks = 2
- The statement tells that each bag[i] is initially filled with rocks[i]. Hence after the bags are filled with the given rocks, the remaining capacity is:
  - remainingCapacity = [1, 1, 0, 1]
- Now, we have to place 2 more rocks in any of the bags. The best way to fill the bags would be such that:
  - Fill up bags that are nearing capacity first
- Now, how do we know which bags are nearing capacity more than the others? Well we can know this by sorting the remaningCapacity. Now, we have:
  - remainingCapacity = [0, 1, 1, 1]
- Now, we can iterate through each of the bags with a count of the number of bags that are full.
- The first bag is already filled. Hence our count = 1.
- The next bag has a capacity of 1. The additional rocks we have are 2. Now we can fill one of the additional rocks which makes the capacity 0. Hence count = 2.
- The third bag also has a capacity of 2. The additional rocks left are 1. We can fill this bag by placing the additional rock. count = 3.
- Now for the final bag, since we have used up all the additional rocks, we cannot fill anymore. Hence we can stop our process.
There is one thing to note though regarding additional rocks.
Since we are sorting the remaining capacity array, we know for sure that if there happen to be a case where the capacity[i] > additionalRocks, then we know that the remaining [i+1,...n] bags also would have a capacity[i] > additionalRocks.
Thus when the condition: capacity[i] > additionalRocks occurs we can stop iterating over the remaining bags.
Hence there would be two cases in total:
- capacity[i] > additionalRocks -> stop iterating over the bags
- capacity[i] <= additionalRocks -> guarantee that the current bag can be filled. Hence count can be incremented.

👩🏽‍💻 Solution - Greedy

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

        for(int i = 0; i<n; i++) {
            cap[i] = capacity[i] - rocks[i];
        }
        Arrays.sort(cap);

        for(int i = 0; i<n; i++) {
            int currCap = cap[i];
            if(currCap == 0) {
                fullBags++;
                continue;
            }

            if(currCap <= additionalRocks) {
                additionalRocks -= currCap;
                fullBags++;
            }
            else {
                break;
            }
        }

        return fullBags;
    }
}

Time Complexity: O(n)
Space Complexity: O(n)

You can find the link to all the solutions on GitHub for this question here: 2279. Maximum Bags With Full Capacity of Rocks.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!

Bharati Subramanian