Minimum Limit of Balls in a Bag - Solution & Explanation
Problem Statement
You are given an integer array nums where the ith bag contains nums[i] balls. You are also given an integer maxOperations.
You can perform the following operation at most maxOperations times:
- Take any bag of balls and divide it into two new bags with a positive number of balls.
- For example, a bag of
5balls can become two new bags of1and4balls, or two new bags of2and3balls.
- For example, a bag of
Your penalty is the maximum number of balls in a bag. You want to minimize your penalty after the operations.
Return the minimum possible penalty after performing the operations.
Example 1:
Input: nums = [9], maxOperations = 2 Output: 3 Explanation: - Divide the bag with 9 balls into two bags of sizes 6 and 3. [9] -> [6,3]. - Divide the bag with 6 balls into two bags of sizes 3 and 3. [6,3] -> [3,3,3]. The bag with the most number of balls has 3 balls, so your penalty is 3 and you should return 3.
Example 2:
Input: nums = [2,4,8,2], maxOperations = 4 Output: 2 Explanation: - Divide the bag with 8 balls into two bags of sizes 4 and 4. [2,4,8,2] -> [2,4,4,4,2]. - Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,4,4,4,2] -> [2,2,2,4,4,2]. - Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,2,2,4,4,2] -> [2,2,2,2,2,4,2]. - Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,2,2,2,2,4,2] -> [2,2,2,2,2,2,2,2]. The bag with the most number of balls has 2 balls, so your penalty is 2, and you should return 2.
Constraints:
1 <= nums.length <= 1051 <= maxOperations, nums[i] <= 109
Approach Overview
Problem Overview: You receive an integer array where each element represents balls in a bag. You may split a bag into two smaller bags up to maxOperations times. The goal is to minimize the maximum number of balls in any bag after performing these operations.
Approach 1: Binary Search on Penalty (O(n log m) time, O(1) space)
The key observation: instead of simulating splits, treat the answer as the maximum allowed balls in any bag (called the penalty). If you guess a penalty p, you can compute how many splits are required so every bag has at most p balls. For a bag with x balls, the number of splits needed is (x - 1) / p. Iterate through the array, sum the required splits, and check if it stays within maxOperations. Because a feasible penalty implies all larger penalties are also feasible, the search space is monotonic. Use binary search between 1 and the maximum value in the array to find the smallest valid penalty.
This method avoids explicit simulation and focuses only on feasibility checks. Each binary search step scans the array once, making it highly efficient even when values are large.
Approach 2: Greedy Approach with Priority Queue (O(k log n) time, O(n) space)
This approach repeatedly splits the bag that currently has the most balls. Use a max-heap from the priority queue family to always access the largest bag quickly. For each operation, remove the largest bag and split it into two smaller bags that reduce the current maximum. Push the resulting bags back into the heap and continue until operations run out.
The intuition is greedy: reducing the largest bag decreases the overall maximum most effectively. While conceptually simple, this approach can be slower when maxOperations is large because every operation triggers heap updates. It also requires tracking intermediate bag sizes.
Recommended for interviews: Binary Search on Penalty is the expected solution. Interviewers look for the insight that the answer lies in a monotonic search space and that you can validate a candidate penalty with a simple linear scan. The greedy heap approach demonstrates good intuition about reducing the maximum element but usually fails to meet optimal performance constraints on large inputs.
Approach 1: Binary Search on Penalty
This approach leverages binary search to efficiently minimize the penalty. The idea is to use binary search to determine the minimum possible 'penalty', where penalty is defined as the maximum number of balls allowed in any bag.
We set our binary search range from 1 to the maximum number of balls in any bag initially. For each mid value (potential penalty), we check if it's possible to achieve this penalty with the given number of operations. We do this by calculating how many operations we'd need to make every bag have at most 'mid' number of balls. If we can do that within the allowed number of operations, we adjust our search range to potentially lower penalties; otherwise, we increase our search range.
The C solution uses a helper function canAchievePenalty which computes whether it's possible to split the balls such that the maximum number of balls in any bag does not exceed the proposed penalty, within the given number of operations. The main function minimumPenalty then uses binary search over this helper to find the minimum possible penalty.
Complexity
Time Complexity: O(n log(max(nums)))
Space Complexity: O(1)
Approach 2: Greedy Approach with Priority Queue
Another approach is to continuously divide the largest bags using a priority queue to keep track of the largest bag sizes. By always splitting the largest bag first, we aim to reduce the penalty faster. This works similarly to the binary search approach in terms of dividing the problem space but uses a different method to handle priorities.
The greedy approach employs priority queue logic indirectly by sorting the array in descending order initially. It repeatedly considers the largest current value, using a strategy similar to the binary search solution.
Complexity
Time Complexity: O(n log n + n log(max(nums)))
Space Complexity: O(1)
Approach 3: Binary Search
This problem requires us to minimize the cost, which is the maximum number of balls in a single bag. As the maximum value increases, the number of operations decreases, making it easier to meet the condition.
Therefore, we can use binary search to enumerate the maximum number of balls in a single bag and determine if it can be achieved within maxOperations operations.
Specifically, we define the left boundary of the binary search as l = 1 and the right boundary as r = max(nums). Then we continuously perform binary search on the middle value mid = \frac{l + r}{2}. For each mid, we calculate the number of operations needed. If the number of operations is less than or equal to maxOperations, it means mid meets the condition, and we update the right boundary r to mid. Otherwise, we update the left boundary l to mid + 1.
Finally, we return the left boundary l.
The time complexity is O(n times log M), where n and M are the length and the maximum value of the array nums, respectively. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
Complexity Comparison
| Approach | Complexity |
|---|---|
| Binary Search on Penalty | Time Complexity: O(n log(max(nums))) |
| Greedy Approach with Priority Queue | Time Complexity: O(n log n + n log(max(nums))) |
| Binary Search | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Binary Search on Penalty | O(n log m) | O(1) | Best general solution when bag sizes can be large and operations are many |
| Greedy with Priority Queue | O(k log n) | O(n) | Useful for conceptual understanding or when operations are relatively small |
Video Solution
Minimum Limit of Balls in a Bag - Leetcode 1760 - Python • NeetCodeIO • 18,898 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum Limit of Balls in a Bag easy or hard?
Minimum Limit of Balls in a Bag Python/Java solution
How to solve Minimum Limit of Balls in a Bag in O(n log m)?
What is the best approach for Minimum Limit of Balls in a Bag?
Is Minimum Limit of Balls in a Bag asked at Google/Amazon/Meta?
What data structure is used in Minimum Limit of Balls in a Bag?
What is the time complexity of Minimum Limit of Balls in a Bag?
Ready to solve this problem?
Practice Minimum Limit of Balls in a Bag with our built-in code editor and test cases.
Practice on FleetCode