LeetCode 1760 - Minimum Limit of Balls in a Bag
You are given several bags of balls, where nums[i] represents how many balls are inside the i-th bag. You are allowed to perform at most maxOperations split operations.
Difficulty: 🟡 Medium
Topics: Array, Binary Search
Solution
Problem Understanding
You are given several bags of balls, where nums[i] represents how many balls are inside the i-th bag. You are allowed to perform at most maxOperations split operations. In one operation, you take a single bag and divide it into two smaller bags, with both new bags containing at least one ball.
The goal is to minimize the penalty, where the penalty is defined as the size of the largest bag after all operations are completed.
Another way to think about the problem is this: after performing some splits, what is the smallest possible value x such that every bag contains at most x balls?
For example, if a bag contains 9 balls and we want every bag to contain at most 3 balls, we can split:
9 -> 6 + 36 -> 3 + 3
Now all bags have size at most 3, and we used exactly 2 operations.
The constraints are very important:
nums.lengthcan be up to10^5- Each
nums[i]can be as large as10^9 maxOperationscan also be as large as10^9
These constraints immediately rule out any simulation that tries all possible ways of splitting bags. The search space is enormous.
The problem guarantees that every bag initially contains at least one ball, and at least one operation is allowed.
Several edge cases are important:
- A single very large bag, where many operations are needed.
- Cases where
maxOperationsis large enough to reduce every bag to size1. - Cases where no meaningful reduction is possible because operations are too limited.
- Large values near
10^9, where inefficient algorithms or overflow-prone arithmetic can fail.
The key challenge is determining whether a candidate maximum bag size is achievable within the allowed number of operations.
Approaches
Brute Force Approach
A brute force strategy would try all possible ways to split bags and track the smallest achievable maximum bag size.
For each operation, we could choose any bag and split it in every possible way. Unfortunately, this creates an exponential number of states. Even a single bag of size 100 has many possible split combinations, and the number of possibilities grows explosively with multiple operations.
Another brute force variation would try every possible penalty value from 1 up to max(nums) and simulate whether it is achievable. While this is better than exploring all split configurations, it is still too slow because max(nums) may be 10^9.
The brute force method is correct because it explicitly explores possible outcomes, but it is computationally infeasible for the given constraints.
Optimal Approach, Binary Search on the Answer
The key insight is that the problem has a monotonic property.
Suppose we ask:
"Can we make every bag have at most x balls using at most maxOperations operations?"
If the answer is yes for some value x, then it will also be yes for any larger value.
For example:
- If we can achieve a maximum bag size of
3, - then we can definitely achieve
4,5,6, and so on.
This monotonic behavior makes the problem ideal for binary search.
We binary search the answer space:
- Minimum possible penalty =
1 - Maximum possible penalty =
max(nums)
For a candidate penalty mid, we compute how many operations are required.
If a bag has size num, and we want every resulting bag to have size at most mid, then the number of required splits is:
$\left\lfloor\frac{num-1}{mid}\right\rfloor$
This works because:
- A bag already smaller than or equal to
midrequires0operations. - Otherwise, we repeatedly split until all parts are at most
mid.
If the total required operations are within maxOperations, then mid is feasible, and we try smaller values.
Otherwise, we need a larger penalty.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | Exponential | Exponential | Tries many split configurations |
| Optimal | O(n log M) | O(1) | Binary search on answer space |
Here:
n = len(nums)M = max(nums)
Algorithm Walkthrough
- Initialize the binary search boundaries.
The smallest possible penalty is 1, because every bag must contain at least one ball.
The largest possible penalty is max(nums), because we can always choose not to split anything.
2. Repeatedly compute the middle value.
Let mid = (left + right) // 2.
This represents the candidate maximum bag size we are testing. 3. Compute how many operations are needed.
For every bag size num, calculate:
$\left\lfloor\frac{num-1}{mid}\right\rfloor$
This gives the minimum number of splits needed so every resulting bag has size at most mid.
Add these values together across all bags. 4. Check feasibility.
If total operations required are less than or equal to maxOperations, then mid is achievable.
Since we want the minimum possible penalty, continue searching the left half. 5. Otherwise, search the right half.
If more operations are needed than allowed, then mid is too small and cannot work.
Increase the lower bound. 6. Continue until the search space collapses.
When left == right, we have found the smallest feasible penalty.
Why it works
The algorithm works because feasibility is monotonic.
If a penalty value x is achievable, then every larger value is also achievable. This creates a sorted true/false search space:
- Small penalties may be impossible.
- Larger penalties become possible.
Binary search efficiently finds the transition point between impossible and possible values.
The operation formula is also optimal because each split increases the number of bags by exactly one, so the formula computes the minimum splits required to reduce a bag into sufficiently small pieces.
Python Solution
from typing import List
class Solution:
def minimumSize(self, nums: List[int], maxOperations: int) -> int:
left = 1
right = max(nums)
while left < right:
mid = (left + right) // 2
operations_needed = 0
for num in nums:
operations_needed += (num - 1) // mid
if operations_needed <= maxOperations:
right = mid
else:
left = mid + 1
return left
The implementation begins by defining the binary search range from 1 to max(nums).
Inside the loop, mid represents the candidate maximum allowed bag size.
The code then iterates through every bag and calculates how many operations are required to reduce that bag so all resulting pieces are at most mid.
The formula:
$\left\lfloor\frac{num-1}{mid}\right\rfloor$
efficiently computes the required splits without explicitly simulating them.
If the total required operations fit within maxOperations, the candidate penalty is feasible, so the algorithm searches for an even smaller answer by moving right.
Otherwise, the penalty is too small, so left is increased.
Eventually, both pointers converge to the minimum feasible penalty.
Go Solution
package main
func minimumSize(nums []int, maxOperations int) int {
left := 1
right := 0
for _, num := range nums {
if num > right {
right = num
}
}
for left < right {
mid := (left + right) / 2
operationsNeeded := 0
for _, num := range nums {
operationsNeeded += (num - 1) / mid
}
if operationsNeeded <= maxOperations {
right = mid
} else {
left = mid + 1
}
}
return left
}
The Go implementation follows exactly the same algorithmic structure as the Python version.
One small difference is that Go does not provide a built-in max() function for slices, so we manually compute the maximum value while initializing right.
Integer division in Go naturally performs floor division for integers, which matches the required formula.
All values safely fit within Go's standard integer range under LeetCode constraints.
Worked Examples
Example 1
Input:
nums = [9]
maxOperations = 2
Initial search range:
| left | right |
|---|---|
| 1 | 9 |
Iteration 1
| mid | operations needed |
|---|---|
| 5 | (9 - 1) // 5 = 1 |
Since 1 <= 2, penalty 5 is feasible.
Update:
| left | right |
|---|---|
| 1 | 5 |
Iteration 2
| mid | operations needed |
|---|---|
| 3 | (9 - 1) // 3 = 2 |
Since 2 <= 2, penalty 3 is feasible.
Update:
| left | right |
|---|---|
| 1 | 3 |
Iteration 3
| mid | operations needed |
|---|---|
| 2 | (9 - 1) // 2 = 4 |
Since 4 > 2, penalty 2 is impossible.
Update:
| left | right |
|---|---|
| 3 | 3 |
Answer:
3
Example 2
Input:
nums = [2,4,8,2]
maxOperations = 4
Initial range:
| left | right |
|---|---|
| 1 | 8 |
Iteration 1
mid = 4
| Bag | Operations |
|---|---|
| 2 | 0 |
| 4 | 0 |
| 8 | 1 |
| 2 | 0 |
Total operations = 1
Feasible, search smaller.
| left | right |
|---|---|
| 1 | 4 |
Iteration 2
mid = 2
| Bag | Operations |
|---|---|
| 2 | 0 |
| 4 | 1 |
| 8 | 3 |
| 2 | 0 |
Total operations = 4
Feasible, search smaller.
| left | right |
|---|---|
| 1 | 2 |
Iteration 3
mid = 1
| Bag | Operations |
|---|---|
| 2 | 1 |
| 4 | 3 |
| 8 | 7 |
| 2 | 1 |
Total operations = 12
Not feasible.
| left | right |
|---|---|
| 2 | 2 |
Answer:
2
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n log M) | Binary search over answer range, scanning all bags each step |
| Space | O(1) | Only constant extra variables are used |
The binary search performs log M iterations, where M is the maximum value in nums.
For each iteration, we scan the entire array once to compute the required number of operations.
Therefore, the total complexity is:
$O(n \log M)$
The algorithm uses only a few integer variables, so the extra space usage is constant.
Test Cases
from typing import List
class Solution:
def minimumSize(self, nums: List[int], maxOperations: int) -> int:
left = 1
right = max(nums)
while left < right:
mid = (left + right) // 2
operations_needed = 0
for num in nums:
operations_needed += (num - 1) // mid
if operations_needed <= maxOperations:
right = mid
else:
left = mid + 1
return left
sol = Solution()
assert sol.minimumSize([9], 2) == 3 # single bag example
assert sol.minimumSize([2, 4, 8, 2], 4) == 2 # provided example
assert sol.minimumSize([1], 1) == 1 # smallest possible input
assert sol.minimumSize([10], 9) == 1 # enough operations to split into ones
assert sol.minimumSize([10], 1) == 5 # only one split allowed
assert sol.minimumSize([1000000000], 1) == 500000000 # very large value
assert sol.minimumSize([7, 17], 2) == 7 # limited operations
assert sol.minimumSize([7, 17], 10) == 3 # many operations available
assert sol.minimumSize([1, 1, 1, 1], 5) == 1 # already optimal
assert sol.minimumSize([3, 6, 9], 3) == 3 # exact operation fit
Test Summary
| Test | Why |
|---|---|
[9], 2 |
Verifies provided example |
[2,4,8,2], 4 |
Verifies multiple bags |
[1], 1 |
Smallest input |
[10], 9 |
Maximum splitting capability |
[10], 1 |
Limited operations |
[1000000000], 1 |
Large integer handling |
[7,17], 2 |
Partial reduction only |
[7,17], 10 |
Aggressive splitting |
[1,1,1,1], 5 |
Already minimal penalty |
[3,6,9], 3 |
Exact feasibility boundary |
Edge Cases
One important edge case is when all bags already satisfy the optimal penalty. For example, nums = [1,1,1]. A buggy implementation might attempt unnecessary operations or incorrectly reduce the answer below 1. This implementation handles the case naturally because the binary search lower bound is 1, and operation counts remain zero.
Another important case is a single extremely large bag, such as nums = [1000000000]. Naive simulation approaches would be far too slow or memory intensive. The binary search solution remains efficient because it never explicitly performs splits. It only computes how many splits would be required mathematically.
A third critical edge case occurs when operations are insufficient to significantly reduce the largest bag. For example, nums = [100] and maxOperations = 1. Some implementations incorrectly assume repeated halving is always possible. Here, only one split may be performed, so the best achievable result is 50. The formula-based feasibility check correctly captures this restriction.
Another subtle case is exact feasibility boundaries, where the required operations equal maxOperations. For example, nums = [8] and maxOperations = 3. We can split into four bags of size 2, using exactly three operations. The implementation correctly uses <= maxOperations, ensuring exact fits are accepted as feasible.