LeetCode#2279_Cover Photo

LeetCode#2279 Maximum Bags With Full Capacity of Rocks

Klook.com
Post Views: 520

LeetCode Contest

This is the second question that appeared in Weekly Contest 294.

LeetCode 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.

LeetCode #2279 official Examples
LeetCode #2279 Constraints

Solution

We got two arrays : capacity and rocks

And for each bag, the difference between two arrays is the number of additional rocks that can be placed.

If the difference of bag [ i ] is 0, than the bag is full.

⭐So, when we can follow these steps to write the code.

  1. Create an array that contains the difference between capacity and rocks.
  2. Sum up all the differences, if additionalRocks amount is above the number, just return the length of array ( no matter rocks or capacity has the same length )
  3. ⭐Sort the difference array ascending, because if we want to get the maximum number of bags that could have full capacity, we should try to place extra rocks from the minimum of the diff array.
  4. Iterate the array, if extra rocks can be placed, than minus the additionalRocks number.

C# Solution

public class Solution {
    public int MaximumBags(int[] capacity, int[] rocks, int additionalRocks) {
      
        int[]diff = new int[capacity.Length];
        long cnt = 0;
        int resCnt = 0;
        
        for(int i=0 ;i<capacity.Length;i++)
        {
            int diffCnt = capacity[i] - rocks[i];
          
            diff[i] = diffCnt;
            cnt+=(long)diffCnt;
        }
 
        if((long)additionalRocks > cnt)
        {
            return capacity.Length;
        }
        
        Array.Sort(diff);

        foreach(var a in diff)
        {
            if(a == 0)
            {
                resCnt+=1;
                continue;
            }

            if(additionalRocks>=a)
            {
                resCnt+=1;
                additionalRocks-= a;
            }
            else
            {
                return resCnt;
            }
        }
        
        return resCnt;
    }
}

⭐Why do we need to use long to save the sum?

That’s because in some test case, the sum is above Int32 MaxValue ( 231 -1 ).

Java Solution

With the same steps, just change some functions.

class Solution {
    public int maximumBags(int[] capacity, int[] rocks, int additionalRocks) {
        int[]diff = new int[capacity.length];
        long cnt = 0;
        int resCnt = 0;
        
        for(int i=0 ;i<capacity.length;i++)
        {
            int diffCnt = capacity[i] - rocks[i];
          
            diff[i] = diffCnt;
            cnt+=(long)diffCnt;
        }
 
        if((long)additionalRocks > cnt)
        {
            return capacity.length;
        }
        
        Arrays.sort(diff);

        for(int a : diff)
        {
            if(a == 0)
            {
                resCnt+=1;
                continue;
            }

            if(additionalRocks>=a)
            {
                resCnt+=1;
                additionalRocks-= a;
            }
            else
            {
                return resCnt;
            }        }
        
        return resCnt; 
    }
}

Python3 Solution

Solution1

class Solution:
    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:
        diff = []
        cnt = 0
        resCnt = 0
        
        for i in range(0,len(capacity)):
            diffCnt = capacity[i] - rocks[i]
            diff.append(diffCnt)
            cnt+=diffCnt

        if additionalRocks > cnt:
            return len(capacity)
        
        diff.sort()

        for a in diff:
            if a == 0:
                resCnt+=1
                continue

            if additionalRocks>=a:
                resCnt+=1
                additionalRocks-= a
            
            else:
                return resCnt
            
        return resCnt

JavaScript Solution

Solution1

/**
 * @param {number[]} capacity
 * @param {number[]} rocks
 * @param {number} additionalRocks
 * @return {number}
 */
var maximumBags = function(capacity, rocks, additionalRocks) {
    var diff = [];
    var cnt = 0;
    var resCnt = 0;
    
    for(let i=0 ;i<capacity.length;i++)
    {
        var diffCnt = capacity[i] - rocks[i];
        
        diff[i] = diffCnt;
        cnt+=diffCnt;
    }

    if(additionalRocks > cnt)
    {
        return capacity.length;
    }
    
    diff.sort(function(a, b){return a-b});
    //diff.sort();
    //diff.forEach(element => console.log(element));

    for(let j = 0; j<diff.length; j++)
    {
        let a = diff[j];
        if(a == 0)
        {
            resCnt+=1;
            continue;
        }

        if(additionalRocks>=a)
        {
            resCnt+=1;
            additionalRocks-= a;
        }
        else
        {
            return resCnt;
        }
    }
    
    return resCnt; 
};

⭐Without settings, Array sort will convert element to string and compare in UTF-16 code units order.

Conclusion

🧡If my solution helps, that is my honor!

✅If you got any problem about the explanation, please feel free to let me know

"A river cuts through rock, not because of its power, but because of its persistence."
                                                                                    James Watkins

Cover Photo – Photo by John Salzarulo on Unsplash

The problem link : Maximum Bags With Full Capacity of Rocks – LeetCode

Reference

Random post

Tags

Related Posts

Leave a Reply

Your email address will not be published. Required fields are marked *