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!