Watch 10 video solutions for Minimum Limit of Balls in a Bag, a medium level problem involving Array, Binary Search. This walkthrough by NeetCodeIO has 18,298 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array nums where the ith bag contains nums[i] balls. You are also given an integer maxOperations.
You can perform the following operation at most maxOperations times:
5 balls can become two new bags of 1 and 4 balls, or two new bags of 2 and 3 balls.Your penalty is the maximum number of balls in a bag. You want to minimize your penalty after the operations.
Return the minimum possible penalty after performing the operations.
Example 1:
Input: nums = [9], maxOperations = 2 Output: 3 Explanation: - Divide the bag with 9 balls into two bags of sizes 6 and 3. [9] -> [6,3]. - Divide the bag with 6 balls into two bags of sizes 3 and 3. [6,3] -> [3,3,3]. The bag with the most number of balls has 3 balls, so your penalty is 3 and you should return 3.
Example 2:
Input: nums = [2,4,8,2], maxOperations = 4 Output: 2 Explanation: - Divide the bag with 8 balls into two bags of sizes 4 and 4. [2,4,8,2] -> [2,4,4,4,2]. - Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,4,4,4,2] -> [2,2,2,4,4,2]. - Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,2,2,4,4,2] -> [2,2,2,2,2,4,2]. - Divide the bag with 4 balls into two bags of sizes 2 and 2. [2,2,2,2,2,4,2] -> [2,2,2,2,2,2,2,2]. The bag with the most number of balls has 2 balls, so your penalty is 2, and you should return 2.
Constraints:
1 <= nums.length <= 1051 <= maxOperations, nums[i] <= 109Problem Overview: You receive an integer array where each element represents balls in a bag. You may split a bag into two smaller bags up to maxOperations times. The goal is to minimize the maximum number of balls in any bag after performing these operations.
Approach 1: Binary Search on Penalty (O(n log m) time, O(1) space)
The key observation: instead of simulating splits, treat the answer as the maximum allowed balls in any bag (called the penalty). If you guess a penalty p, you can compute how many splits are required so every bag has at most p balls. For a bag with x balls, the number of splits needed is (x - 1) / p. Iterate through the array, sum the required splits, and check if it stays within maxOperations. Because a feasible penalty implies all larger penalties are also feasible, the search space is monotonic. Use binary search between 1 and the maximum value in the array to find the smallest valid penalty.
This method avoids explicit simulation and focuses only on feasibility checks. Each binary search step scans the array once, making it highly efficient even when values are large.
Approach 2: Greedy Approach with Priority Queue (O(k log n) time, O(n) space)
This approach repeatedly splits the bag that currently has the most balls. Use a max-heap from the priority queue family to always access the largest bag quickly. For each operation, remove the largest bag and split it into two smaller bags that reduce the current maximum. Push the resulting bags back into the heap and continue until operations run out.
The intuition is greedy: reducing the largest bag decreases the overall maximum most effectively. While conceptually simple, this approach can be slower when maxOperations is large because every operation triggers heap updates. It also requires tracking intermediate bag sizes.
Recommended for interviews: Binary Search on Penalty is the expected solution. Interviewers look for the insight that the answer lies in a monotonic search space and that you can validate a candidate penalty with a simple linear scan. The greedy heap approach demonstrates good intuition about reducing the maximum element but usually fails to meet optimal performance constraints on large inputs.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Binary Search on Penalty | O(n log m) | O(1) | Best general solution when bag sizes can be large and operations are many |
| Greedy with Priority Queue | O(k log n) | O(n) | Useful for conceptual understanding or when operations are relatively small |