Maximum Bags With Full Capacity of Rocks

Medium
1154.

Maximum Bags With Full Capacity of Rocks

Maximum Bags With Full Capacity of Rocks is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.

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.length
  • 1 <= n <= 5 * 10^4
  • 1 <= capacity[i] <= 10^9
  • 0 <= rocks[i] <= capacity[i]
  • 1 <= additionalRocks <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} capacity
 * @param {number[]} rocks
 * @param {number} additionalRocks
 * @return {number}
 */
var maximumBags = function(capacity, rocks, additionalRocks) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.length
  • 1 <= n <= 5 * 10^4
  • 1 <= capacity[i] <= 10^9
  • 0 <= rocks[i] <= capacity[i]
  • 1 <= additionalRocks <= 10^9

Hints for Maximum Bags With Full Capacity of Rocks

  1. Hint 1

    Only the shortfall capacity[i] - rocks[i] of each bag matters.

  2. Hint 2

    To complete as many bags as possible with a fixed budget, which bags should you complete first?

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

  1. Compute need[i] = capacity[i] - rocks[i] for every bag.
  2. Sort need ascending.
  3. Walk the sorted list, subtracting each shortfall from the remaining rocks while it fits, and count the bags completed.
  4. 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 full

Java

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