Maximum Bags With Full Capacity of Rocks - Practice Coding Problems

Maximum Bags With Full Capacity of Rocks - Problem

You have n bags numbered from 0 to n - 1. You are given two 0-indexed integer arrays capacity and rocks. The i-th 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.

Input & Output

Example 1 — Basic Case

$ Input: capacity = [2,3,4,5], rocks = [1,0,1,4], additionalRocks = 2

› Output: 2

💡 Note: Bags need [1,3,3,1] rocks respectively. With 2 additional rocks, we can fill bags 0 and 3 (need 1 each), giving us 2 full bags total.

Example 2 — Already Full Bags

$ Input: capacity = [10,2,2], rocks = [2,2,0], additionalRocks = 100

› Output: 3

💡 Note: Bag 1 is already full. Bag 0 needs 8 rocks, bag 2 needs 2 rocks. We can fill both with 100 additional rocks, so all 3 bags are full.

Example 3 — Insufficient Rocks

$ Input: capacity = [5,5,5], rocks = [0,0,0], additionalRocks = 4

› Output: 0

💡 Note: Each bag needs 5 rocks to be full, but we only have 4 additional rocks. Cannot fill any bag completely.

Constraints

1 ≤ n ≤ 10⁵
capacity.length == rocks.length == n
1 ≤ capacity[i] ≤ 10⁹
0 ≤ rocks[i] ≤ capacity[i]
1 ≤ additionalRocks ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Bags with capacities [2,3,4,5], current rocks [1,0,1,4], additional rocks: 2

Calculate Needs

Each bag needs [1,3,3,1] more rocks to be full

Greedy Fill

Fill bags needing 1 rock each first, result: 2 bags full

Key Takeaway

🎯 Key Insight: Greedy approach works - always fill the bags requiring the fewest additional rocks first

Asked in

a Amazon 35 G Google 28 M Microsoft 22 f Meta 18

The key insight is to use a greedy approach: always fill the bags that require the fewest additional rocks first. Calculate rocks needed for each bag, sort by requirement, then fill in ascending order until additional rocks run out. Best approach is Greedy Sorting. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(additionalRocks^n)	O(1)	Try every possible way to distribute additional rocks among bags
Greedy - Fill Bags Needing Fewest Rocks First	O(n log n)	O(n)	Sort bags by how many rocks they need, then fill from least to most needed

Brute Force - Try All Combinations — Algorithm Steps

Calculate rocks needed for each bag
Generate all possible distributions of additional rocks
For each distribution, count how many bags become full
Return the maximum count found

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Needs

Find how many rocks each bag needs to be full

Try All Combinations

Recursively try filling or not filling each bag

Find Maximum

Return the distribution that fills the most bags

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int backtrack(int* needed, int n, int index, int remainingRocks, int filledCount) {
    if (index == n) {
        return filledCount;
    }
    
    int maxFilled = filledCount;
    // Try not filling this bag
    maxFilled = max(maxFilled, backtrack(needed, n, index + 1, remainingRocks, filledCount));
    
    // Try filling this bag if we have enough rocks
    if (remainingRocks >= needed[index]) {
        maxFilled = max(maxFilled, backtrack(needed, n, index + 1, remainingRocks - needed[index], filledCount + 1));
    }
    
    return maxFilled;
}

int solution(int* capacity, int* rocks, int n, int additionalRocks) {
    int* needed = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        needed[i] = max(0, capacity[i] - rocks[i]);
    }
    
    int result = backtrack(needed, n, 0, additionalRocks, 0);
    free(needed);
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse capacity array
    int capacity[100];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL && n < 100) {
        capacity[n++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    fgets(line, sizeof(line), stdin);
    
    // Parse rocks array
    int rocks[100];
    int m = 0;
    token = strtok(line, "[,]");
    while (token != NULL && m < 100) {
        rocks[m++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    int additionalRocks;
    scanf("%d", &additionalRocks);
    
    printf("%d\n", solution(capacity, rocks, n, additionalRocks));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(additionalRocks^n)

We try all ways to distribute additionalRocks among n bags, leading to exponential combinations

✓ Linear Growth

Space Complexity

O(1)

Only using variables to track current distribution and maximum count

✓ Linear Space

25.6K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler