Skip to main content

2279. Maximum Bags With Full Capacity of Rocks

This page provides solutions for the leetcode problem Leetcode 2279. Maximum Bags With Full Capacity of Rocks.

Problem Explanation

The problem asks us to determine the maximum number of bags that can be filled to their full capacity after adding extra rocks. The capacity of each bag is represented by the capacity\text{capacity} array, and the number of rocks already in each bag is provided in the rocks\text{rocks} array.

Solution

This problem can be solved using the Greedy technique. More such questions can be found here.

class Solution {
public int maximumBags(int[] capacity, int[] rocks, int additionalRocks) {
int n = rocks.length;
int[] requiredRocks = new int[n];
for(int i = 0; i < n; i++) required[i] = capacity[i] - rocks[i];

Arrays.sort(required);
int index = 0;
while(additionalRocks > 0 && index < required.length) {
if(additionalRocks >= required[index]) additionalRocks -= required[index++];
else break;
}
return index;
}
}

Complexity

Let's say there are N\text{N} elements in a rocks\text{rocks} array.

Time Complexity

Time complexity of O(N log N)\text{O}(\text{N} \ \text{log} \ \text{N}) for sorting capacity\text{capacity} array and O(N)\text{O}(\text{N}) for calculating maximum number of bags.

O(N log N)\text{O}(\text{N} \ \text{log} \ \text{N})

Space Complexity

The solution uses O(N)\text{O}(\text{N}) space to calculate required rocks for each bag.

O(N)\text{O}(\text{N})