⚡Flashcard Drill➔
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

  1. Binary search on the maximum bag size x: "can every bag be reduced to at most x with at most maxOperations splits" is monotone.
  2. A bag with b balls needs ceil(b / x) - 1 splits, which simplifies to (b - 1) // x.
  3. Sum the splits and compare with maxOperations.
  4. 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 // mid instead of (b - 1) // mid: the number of splits is ceil(b / mid) - 1, which equals (b - 1) // mid -- the -1 is 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 - 1 when feasible: could skip the optimum.
  • Assuming maxOperations must 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.
🎯 Drill This Card Now➔

🧩 Related Binary Search Problems