Skip to main content
Talentd

Maximum Bags With Full Capacity of Rocks - Solution & Explanation

MediumArrayGreedySorting13 min readAsked at: Amazon
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given arrays capacity and rocks where each bag has a maximum capacity and a current number of rocks. You also have additionalRocks to distribute. The goal is to maximize how many bags reach full capacity after distributing these extra rocks.

The key observation: every bag requires a certain number of additional rocks to become full. If you always fill the bags that require the fewest extra rocks first, you maximize the number of completed bags.

Approach 1: Greedy with Sorting (O(n log n) time, O(n) space)

Compute how many rocks each bag still needs: required[i] = capacity[i] - rocks[i]. Store these values in an array and sort it in ascending order. Then iterate through the sorted requirements and greedily fill the cheapest bags first. For each requirement, subtract it from additionalRocks. If enough rocks remain, the bag becomes full and the count increases; otherwise stop. Sorting ensures you always prioritize the smallest deficits, which maximizes the number of bags filled. This approach uses ideas from greedy algorithms and sorting, and works well because the cost of filling each bag is independent.

Approach 2: Priority Queue (Min-Heap) (O(n log n) time, O(n) space)

Instead of sorting all deficits upfront, push each required value into a min-heap. A min-heap always exposes the smallest deficit at the top. Repeatedly pop the smallest value and check whether additionalRocks can cover it. If yes, subtract it and increment the number of full bags. If not, stop because every remaining bag requires at least as many rocks. The heap approach models the same greedy decision but retrieves the next best candidate dynamically. It relies on a heap structure and is conceptually useful when data arrives incrementally or when you want explicit priority ordering.

Recommended for interviews: The greedy sorting solution is typically what interviewers expect. It shows you recognized the optimization strategy: fill the smallest deficits first. Implementing it with a sorted array is simple and efficient at O(n log n). The heap approach demonstrates familiarity with priority queues, but it adds extra structure without improving asymptotic complexity.

This problem is a classic greedy allocation pattern: compute cost differences, sort them, and spend limited resources in the most efficient order. Similar reasoning appears frequently in array optimization problems.

Approach 1: Greedy Approach with Sorting

This approach involves calculating how many rocks each bag needs to be full. Then, we sort these requirements in increasing order. By doing so, we ensure we fill the bags requiring fewer rocks first, maximizing the number of fully filled bags. We iterate through these sorted requirements, and while we have enough additional rocks, we fill these bags, counting the number of bags that can be fully filled.

This Python function calculates the number of rocks needed for each bag, sorts these requirements, then iteratively fills as many bags as possible using the given additional rocks, counting how many bags achieve full capacity.

Code

PythonJavaC++CC#JavaScript

Python

Java

C++

C

C#

JavaScript

Complexity

Time Complexity: O(n log n), due to sorting the differences.
Space Complexity: O(n), for storing the differences array.

Try this approach in the editor →

Approach 2: Priority Queue (Min-Heap) Approach

Instead of sorting the entire list of differences, we can use a min-heap (priority queue) to keep track of the current smallest difference that can be fulfilled with the additional rocks. This way, we continuously fill the bags requiring the least rocks at the minimum overhead cost of tree-based structure operations. While more sophisticated, this method matches the efficiency of the sorting approach for this problem's expected input size.

This solution uses a min-heap to efficiently decide which bags to fill with additional rocks by always selecting the currently least required amount, popping it from the heap and counting the full bag if successfully filled.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n log n), predominantly due to building and maintaining the heap.
Space Complexity: O(n), for the heap storage.

Try this approach in the editor →

Approach 3: Sorting + Greedy

First, we calculate the remaining capacity of each bag, then sort the remaining capacities. Next, we traverse the remaining capacities from smallest to largest, putting the extra stones into the bags until the extra stones are used up or the remaining capacities of the bags are exhausted. Finally, we return the number of bags at this point.

Time complexity is O(n times log n), and space complexity is O(log n). Here, n is the number of bags.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach with Sorting

Time Complexity: O(n log n), due to sorting the differences.
Space Complexity: O(n), for storing the differences array.

Priority Queue (Min-Heap) Approach

Time Complexity: O(n log n), predominantly due to building and maintaining the heap.
Space Complexity: O(n), for the heap storage.

Sorting + Greedy—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy with SortingO(n log n)O(n)Best general solution. Sort deficits and greedily fill smallest requirements first.
Priority Queue (Min-Heap)O(n log n)O(n)Useful when processing bags dynamically or when explicit priority ordering is preferred.

Video Solution

Maximum Bags With Full Capacity of Rocks : Explanation ➕ Live Coding 🧑🏻‍💻👩🏻‍💻 • codestorywithMIK • 7,190 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Bags With Full Capacity of Rocks easy or hard?
The problem is rated Medium on LeetCode. The implementation is straightforward once you recognize the greedy insight of filling the smallest deficits first, but identifying that strategy can take some reasoning during interviews.
Maximum Bags With Full Capacity of Rocks Python/Java solution
The typical Python or Java implementation computes capacity[i] - rocks[i], sorts the deficits, and iterates while subtracting from additionalRocks. Each bag that can be fully filled increases the answer counter. This greedy implementation runs in O(n log n) time.
How to solve Maximum Bags With Full Capacity of Rocks in O(n)?
A strict O(n) solution is not typical because the deficits must be ordered to ensure the greedy choice. Most correct implementations sort the required rocks, giving O(n log n) time. If the range of deficits were limited, counting or bucket techniques could theoretically reduce sorting cost.
What is the best approach for Maximum Bags With Full Capacity of Rocks?
The optimal approach uses a greedy strategy with sorting. Compute how many rocks each bag still needs, sort these deficits, and fill the smallest ones first using the available additional rocks. This guarantees the maximum number of bags filled because cheaper completions are prioritized.
Is Maximum Bags With Full Capacity of Rocks asked at Google/Amazon/Meta?
Greedy allocation and resource distribution problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. While the exact question may vary, the pattern of sorting deficits and greedily filling them is common in coding interviews.
What data structure is used in Maximum Bags With Full Capacity of Rocks?
The main structures used are arrays for storing deficits and optionally a priority queue (min-heap). The greedy solution sorts an array of required rocks, while an alternative implementation uses a min-heap to repeatedly extract the smallest requirement.
What is the time complexity of Maximum Bags With Full Capacity of Rocks?
The optimal solution runs in O(n log n) time due to sorting the array of required rocks. After sorting, a single linear scan distributes the extra rocks. Space complexity is O(n) if a separate array is used to store deficits.

Ready to solve this problem?

Practice Maximum Bags With Full Capacity of Rocks with our built-in code editor and test cases.

Practice on FleetCode
Previous

Capacity To Ship Packages Within D Days

Next

Maximum Units on a Truck