2279. Maximum Bags With Full Capacity of Rocks LeetCode Solution

In this guide, you will get 2279. Maximum Bags With Full Capacity of Rocks LeetCode Solution with the best time and space complexity. The solution to Maximum Bags With Full Capacity of Rocks problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximum Bags With Full Capacity of Rocks solution in C++
Maximum Bags With Full Capacity of Rocks solution in Java
Maximum Bags With Full Capacity of Rocks solution in Python
Additional Resources

2279. Maximum Bags With Full Capacity of Rocks LeetCode Solution image

Problem Statement of Maximum Bags With Full Capacity of Rocks

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

Complexity Analysis

Time Complexity: O(\texttt{sort})
Space Complexity: O(n)

2279. Maximum Bags With Full Capacity of Rocks LeetCode Solution in C++

class Solution {
 public:
  int maximumBags(vector<int>& capacity, vector<int>& rocks,
                  int additionalRocks) {
    const int n = capacity.size();
    vector<int> diff(n);

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

    ranges::sort(diff);

    for (int i = 0; i < n; ++i) {
      if (diff[i] > additionalRocks)
        return i;
      additionalRocks -= diff[i];
    }

    return n;
  }
};
/* code provided by PROGIEZ */

2279. Maximum Bags With Full Capacity of Rocks LeetCode Solution in Java

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

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

    Arrays.sort(diff);

    for (int i = 0; i < n; ++i) {
      if (diff[i] > additionalRocks)
        return i;
      additionalRocks -= diff[i];
    }

    return n;
  }
}
// code provided by PROGIEZ

2279. Maximum Bags With Full Capacity of Rocks LeetCode Solution in Python

class Solution:
  def maximumBags(
      self,
      capacity: list[int],
      rocks: list[int],
      additionalRocks: int,
  ) -> int:
    for i, d in enumerate(sorted([c - r for c, r in zip(capacity, rocks)])):
      if d > additionalRocks:
        return i
      additionalRocks -= d
    return len(capacity)
 # code by PROGIEZ