Minimum Limit of Balls in a Bag: Binary Search on Answer Pattern

Minimum Limit of Balls in a Bag is LeetCode 1760. You are given an integer array nums where each element represents a bag containing that many balls. You are also given an integer maxOperations. In each operation, you can pick any bag, split it into two new bags (the total balls across the two new bags must equal the original). After performing at most maxOperations splits, you want to minimize the maximum number of balls in any single bag. Return that minimized maximum.

This is a textbook example of the "binary search on the answer" pattern. Instead of simulating which bags to split and how, you flip the question: for a given maximum bag size, can you achieve it within the allowed number of operations?

Why this problem matters

Binary search on the answer is one of the most important patterns in competitive programming and coding interviews. The idea is simple but powerful: when the answer lies in a range and you can efficiently check whether a candidate answer is feasible, you can binary search that range instead of trying every possibility.

This pattern appears in dozens of LeetCode problems. Koko Eating Bananas, Split Array Largest Sum, Capacity to Ship Packages. They all share the same skeleton. Minimum Limit of Balls in a Bag is another clean example, and mastering it means you can recognize and solve this entire family of problems.

The key insight

Do not think about which bags to split or in what order. Instead, ask a different question: "If I want every bag to have at most t balls, how many operations do I need?"

For a single bag of size n with target t, you need to split it into ceil(n / t) pieces. That takes ceil(n / t) - 1 operations (each split adds one piece). Sum this across all bags to get the total operations required.

Now the problem is monotonic. If you can achieve a max bag size of t, you can definitely achieve t + 1 (just do fewer splits). If you cannot achieve t, you certainly cannot achieve t - 1 (that would require even more splits). This monotonic structure is exactly what binary search needs.

The solution

def minimum_size(nums, max_operations):
    lo, hi = 1, max(nums)

    while lo < hi:
        mid = lo + (hi - lo) // 2
        ops = sum((n - 1) // mid for n in nums)

        if ops <= max_operations:
            hi = mid
        else:
            lo = mid + 1

    return lo

The search range is [1, max(nums)]. A target of 1 means every bag has at most 1 ball (maximum splitting). A target of max(nums) means no splitting at all.

For each candidate mid, we compute the total operations needed using (n - 1) // mid for each bag. This is the integer version of ceil(n / mid) - 1. If the total operations fit within max_operations, the target is feasible and we try smaller. Otherwise, we need a larger target.

Visual walkthrough

Let's binary search for the minimum valid target with nums = [9, 2, 7] and maxOperations = 2. The search range is [1, 9].

Four steps. Instead of trying all 9 possible targets, we checked 3 candidates and found the answer. For larger ranges (say up to a billion), binary search still finishes in about 30 iterations. That is the power of logarithmic search.

Complexity analysis

The binary search runs O(log(max(nums))) iterations. Each iteration loops through all n bags to compute the total operations. So the total time is O(n * log(max(nums))).

Space is O(1) since we only use a few variables. No extra data structures are needed.

The building blocks

1. Binary search on the answer

The template for this pattern is always the same. Define a range of candidate answers, write a feasibility check, and binary search for the boundary.

lo, hi = min_possible, max_possible

while lo < hi:
    mid = lo + (hi - lo) // 2
    if is_feasible(mid):
        hi = mid
    else:
        lo = mid + 1

return lo

When you are minimizing, use hi = mid when feasible (the current value might be the answer) and lo = mid + 1 when infeasible (you need something strictly larger). The loop condition is lo < hi, and the answer is lo when they converge.

2. Feasibility check with ceiling division

The feasibility check for this problem counts total splits needed across all bags. For each bag of size n with target t, the splits required are ceil(n / t) - 1.

def is_feasible(nums, target, max_ops):
    ops = sum((n - 1) // target for n in nums)
    return ops <= max_ops

The key formula is (n - 1) // target. When n is already at most target, this evaluates to 0 (no split needed). When n is larger, it gives the exact number of splits to break the bag into pieces of size target or smaller.

Edge cases

• All bags already small: if every bag has at most 1 ball, the answer is 1 with zero operations.
• maxOperations = 0: no splits allowed, so the answer is simply max(nums).
• Single bag: nums = [10], maxOperations = 2. You can split into 3 pieces at most, so the answer is ceil(10 / 3) = 4.
• Large values: nums[i] can be up to 10^9, but binary search handles this in about 30 iterations.
• All bags the same size: the operations spread evenly. The formula still works without special handling.

From understanding to recall

You probably see the pattern now. Binary search the answer range, check feasibility at each midpoint, narrow down to the smallest valid target. The code is short, about 8 lines.

But writing it under pressure is different from understanding it. Was the ceiling division (n - 1) // mid or (n + mid - 1) // mid? Do you set hi = mid or hi = mid - 1? These details matter, and they slip away without practice.

Spaced repetition locks them in. You write the solution from scratch today, again tomorrow, then in a few days. After a handful of rounds, the template is muscle memory. You do not have to rederive it during an interview. You just write it.

Related posts

• Koko Eating Bananas - The classic binary search on answer problem with the same template
• Split Array Largest Sum - Binary search on the answer applied to array partitioning
• Binary Search - The foundational binary search pattern

Minimum Limit of Balls in a Bag is a clean example of the binary search on answer family. Once you can write this solution from memory, you have the template for an entire category of problems. CodeBricks uses spaced repetition to help you drill these patterns until they stick, so the next time you see a "minimize the maximum" problem, you recognize it immediately and write the solution without hesitation.