Minimum Limit of Balls in a Bag

Medium Binary Search Binary Search on Answer Space Original on LeetCode

Reported atFlipkart

Minimum Limit of Balls in a Bag is a medium binary search problem solved with the binary search on answer space pattern. The best approach, optimal (binary search on the penalty), runs in O(n · log(max(nums))) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (try every penalty from 1 upward) up.

Problem

You are given an array nums where nums[i] is the number of balls in the i-th bag, and an integer maxOperations.

In one operation you pick any bag and split it into two new bags, each holding a positive number of balls (their counts add up to the original). You may perform at most maxOperations operations.

The penalty is the number of balls in the fullest bag. Return the smallest penalty you can reach.

Examples

Example 1

Input
nums = [12], maxOperations = 3
Output
3
Why
Three splits turn 12 into four bags of 3: 12 → 3 + 9 → 3 + 3 + 6 → 3 + 3 + 3 + 3.

Example 2

Input
nums = [5, 8, 3], maxOperations = 2
Output
4
Why
Split 5 into 4 + 1 and 8 into 4 + 4. A limit of 3 would need 1 + 2 = 3 splits.

Example 3

Input
nums = [7, 7], maxOperations = 0
Output
7
Why
No splits allowed, so the penalty is just the largest bag.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 0 <= maxOperations <= 10^9

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (try every penalty from 1 upward)O(max(nums) · n)O(1)
Optimal (binary search on the penalty)O(n · log(max(nums)))O(1)

1Brute force (try every penalty from 1 upward)

TimeO(max(nums) · n)Up to max(nums) candidate penalties, each costing a pass over n bags.
SpaceO(1)Only counters.

For p = 1, 2, 3, … compute how many splits are needed to make every bag at most p. The first p that needs at most maxOperations splits is the answer.

  1. For p from 1 to max(nums): need = sum of (x - 1) / p over all bags.
  2. Return the first p with need <= maxOperations (p = max(nums) always works with 0 splits).
class Solution {
    public int minimumSize(int[] nums, int maxOperations) {
        int max = 0;
        for (int x : nums) max = Math.max(max, x);
        for (int p = 1; p < max; p++) {
            long need = 0;
            for (int x : nums) need += (x - 1) / p;
            if (need <= maxOperations) return p;
        }
        return max;
    }
}

2Optimal (binary search on the penalty)

TimeO(n · log(max(nums)))About 30 binary search steps for values up to 10^9, each a pass over the n bags.
SpaceO(1)Only the search bounds and a running sum.

The number of splits needed for penalty p never increases as p grows, so feasibility is monotone. Binary search the smallest feasible p in [1, max(nums)], checking each candidate in one pass.

  1. lo = 1, hi = max(nums) (always feasible).
  2. While lo < hi: mid = lo + (hi - lo) / 2; need = sum of (x - 1) / mid (64-bit).
  3. If need <= maxOperations, hi = mid (mid works, maybe smaller does too); else lo = mid + 1.
  4. Return lo.
class Solution {
    public int minimumSize(int[] nums, int maxOperations) {
        int lo = 1, hi = 0;
        for (int x : nums) hi = Math.max(hi, x);
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            long need = 0;
            for (int x : nums) need += (x - 1) / mid;
            if (need <= maxOperations) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
}

Edge cases to test

  • No operations available: answer is max(nums)
  • Enough operations to make every bag size 1
  • A single huge bag
  • The total split count can exceed 32 bits (10^5 bags × 10^9 / 1): sum it in a 64-bit integer

Hints

Hint 1

Fix a target penalty p. How many splits does one bag of x balls need so that every piece is at most p?

Hint 2

A bag of x needs ceil(x / p) - 1 = (x - 1) / p splits (integer division), and splits in different bags are independent.

Hint 3

The split count only goes down as p grows. Binary search for the smallest p whose total fits within maxOperations.

FAQ

What is the best time complexity for Minimum Limit of Balls in a Bag?

Optimal (binary search on the penalty) runs in O(n · log(max(nums))) time and O(1) extra space. About 30 binary search steps for values up to 10^9, each a pass over the n bags.

Which pattern does Minimum Limit of Balls in a Bag use?

It is a binary search problem that uses the binary search on answer space pattern. Other problems with the same pattern: Koko Eating Bananas, Minimum Number of Days to Make m Bouquets, Separate Squares I.

Is there a brute force solution for Minimum Limit of Balls in a Bag?

Yes. Brute force (try every penalty from 1 upward) takes O(max(nums) · n) time and O(1) space. For p = 1, 2, 3, … compute how many splits are needed to make every bag at most p.

Which edge cases should I test for Minimum Limit of Balls in a Bag?

No operations available: answer is max(nums); Enough operations to make every bag size 1; A single huge bag; The total split count can exceed 32 bits (10^5 bags × 10^9 / 1): sum it in a 64-bit integer.