Maximum Bags With Full Capacity of Rocks — Solution
Maximum Bags With Full Capacity of Rocks solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximum Bags With Full Capacity of Rocks is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Greedy
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
There are n bags. Bag i can hold at most capacity[i] rocks and currently holds rocks[i] of them. You also have additionalRocks spare rocks that you may drop into any bags you like.
A bag is full when it holds exactly its capacity. Return the maximum number of bags that can be full after you place some (or all) of the spare rocks.
Example 1
Input: capacity = [3,5,2,6], rocks = [1,5,0,3], additionalRocks = 4
Output: 3
Explanation: Bag 1 is already full. Spend 2 rocks on bag 0 and 2 on bag 2. Bag 3 would need 3 more.
Example 2
Input: capacity = [10,4,7], rocks = [2,4,6], additionalRocks = 1
Output: 2
Explanation: Bag 1 is full and one rock completes bag 2.
Example 3
Input: capacity = [9], rocks = [0], additionalRocks = 5
Output: 0
Constraints
n == capacity.length == rocks.length1 <= n <= 5 * 10^41 <= capacity[i] <= 10^90 <= rocks[i] <= capacity[i]1 <= additionalRocks <= 10^9
Hints for Maximum Bags With Full Capacity of Rocks
Hint 1
Only the shortfall
capacity[i] - rocks[i]of each bag matters.Hint 2
To complete as many bags as possible with a fixed budget, which bags should you complete first?
Hint 3
Sort the shortfalls ascending and fill bags until the next shortfall exceeds what is left.
How to solve Maximum Bags With Full Capacity of Rocks
Every bag costs its shortfall to complete and every completed bag is worth the same, so the cheapest bags should be completed first.
Approach
- Compute
need[i] = capacity[i] - rocks[i]for every bag. - Sort
needascending. - Walk the sorted list, subtracting each shortfall from the remaining rocks while it fits, and count the bags completed.
- Stop at the first shortfall that does not fit.
Why it works
Suppose an optimal plan completes k bags. Replacing them by the k cheapest bags never costs more, so the k smallest shortfalls also fit in the budget. Hence the greedy prefix of the sorted shortfalls reaches the optimum.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- Bags that are already full have shortfall 0 and count for free.
- Once a shortfall does not fit, the larger ones after it will not either — stop.
- Summing all shortfalls can overflow 32-bit; subtracting from the budget only while it fits stays in range.
Reference solution
Python
from typing import List
def maximumBags(capacity: List[int], rocks: List[int], additionalRocks: int) -> int:
need = sorted(c - r for c, r in zip(capacity, rocks))
left = additionalRocks
full = 0
for d in need:
if d > left:
break
left -= d
full += 1
return fullJava
public static int maximumBags(int[] capacity, int[] rocks, int additionalRocks) {
int n = capacity.length;
int[] need = new int[n];
for (int i = 0; i < n; i++) need[i] = capacity[i] - rocks[i];
Arrays.sort(need);
int left = additionalRocks, full = 0;
for (int d : need) {
if (d > left) break;
left -= d;
full++;
}
return full;
}C++
int maximumBags(vector<int>& capacity, vector<int>& rocks, int additionalRocks) {
int n = capacity.size();
vector<int> need(n);
for (int i = 0; i < n; i++) need[i] = capacity[i] - rocks[i];
sort(need.begin(), need.end());
int left = additionalRocks, full = 0;
for (int d : need) {
if (d > left) break;
left -= d;
full++;
}
return full;
}JavaScript
var maximumBags = function(capacity, rocks, additionalRocks) {
var need = [];
for (var i = 0; i < capacity.length; i++) need.push(capacity[i] - rocks[i]);
need.sort(function(a, b) { return a - b; });
var left = additionalRocks, full = 0;
for (var j = 0; j < need.length; j++) {
if (need[j] > left) break;
left -= need[j];
full++;
}
return full;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms