NeetCode #282LC-1760MediumBinary Search
← Back to All Problems#282 · #1760 · Minimum Limit of Balls in a Bag(袋子里最少数目的球)
📌 Problem Statement & Constraints
You are given an integer array
nums where nums[i] is the number of balls in the i-th bag, and an integer maxOperations. Each operation splits one bag into two bags with positive counts. Return the minimum possible maximum bag size after at most maxOperations operations. Constraints: 1 <= nums.length <= 10^5, 1 <= maxOperations, nums[i] <= 10^9.💡 Core Algorithmic Approaches
- Binary search on the maximum bag size
x: "can every bag be reduced to at mostxwith at mostmaxOperationssplits" is monotone. - A bag with
bballs needsceil(b / x) - 1splits, which simplifies to(b - 1) // x. - Sum the splits and compare with
maxOperations. - The lower bound is 1 and the upper bound is
max(nums).
💻 Benchmark Python3 Implementation
class Solution:
def minimumSize(self, nums: List[int], maxOperations: int) -> int:
lo, hi = 1, max(nums)
while lo < hi:
mid = (lo + hi) // 2
# splits needed to bring every bag down to at most mid
ops = sum((b - 1) // mid for b in nums)
if ops <= maxOperations:
hi = mid # feasible -> try a smaller cap
else:
lo = mid + 1
return lo⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log(max(nums))): each feasibility check is O(n).
💾 Space Complexity
O(1): a few scalars.
⚠️ Interview Pitfalls & Follow-ups
- Using
b // midinstead of(b - 1) // mid: the number of splits isceil(b / mid) - 1, which equals(b - 1) // mid-- the-1is essential, otherwise a bag that already fits is counted as needing a split. - Using
ceil(b / mid): that counts pieces, not splits; the split count is one less. - Using
hi = mid - 1when feasible: could skip the optimum. - Assuming
maxOperationsmust be used exactly: at most, so extra operations are simply unused.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.