Minimum Limit of Balls in a Bag solution and explanation
Google
9 more videos on this problem
Minimum Limit of Balls in a Bag - Leetcode 1760 - PythonNeetCodeIO · 16:25 · 18K views
Minimum Limit of Balls in a Bag | Detailed | Why Binary Search | Leetcode 1760 | codestorywithMIKcodestorywithMIK · 42:13 · 13K views
Leetcode 1760. Minimum Limit of Balls in a BagFraz · 13:39 · 12K views
Minimum Limit of Balls in a Bag | Leetcode 1760Techdose · 22:31 · 6K views
LeetCode 1760. Minimum Limit of Balls in a Bag | Weekly Contest 228 | Algorithm Explained | C++Cherry Coding [IIT-G] · 10:29 · 4K views
1760. Minimum Limit of Balls in a Bag | How to think of Binary Search? | Binary Search on AnswerAryan Mittal · 16:35 · 3K views
花花酱 LeetCode 1760. Minimum Limit of Balls in a Bag - 刷题找工作 EP384Hua Hua · 17:38 · 3K views
LeetCode 1760. Minimum Limit of Balls in a BagHappy Coding · 15:11 · 2K views
1760. Minimum Limit of Balls in a Bag | leetcode daily challenge | shashcode | shashwat tiwariShashCode · 24:33 · 2K views
LeetCode 1760 Minimum Limit of Balls in a Bag | Binary Search on Answer Space | Amazon | FlipkartCode Harmony · 19:11 · 629 views
The problem
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:
- Take any bag of balls and divide it into two new bags with a positive number of balls.
- For example, a bag of
5balls can become two new bags of1and4balls, or two new bags of2and3balls.
- For example, a bag of
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] <= 109
Approach overview
Problem 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 1: Binary Search on Penalty
This approach leverages binary search to efficiently minimize the penalty. The idea is to use binary search to determine the minimum possible 'penalty', where penalty is defined as the maximum number of balls allowed in any bag.
We set our binary search range from 1 to the maximum number of balls in any bag initially. For each mid value (potential penalty), we check if it's possible to achieve this penalty with the given number of operations. We do this by calculating how many operations we'd need to make every bag have at most 'mid' number of balls. If we can do that within the allowed number of operations, we adjust our search range to potentially lower penalties; otherwise, we increase our search range.
def can_achieve_penalty(nums, max_operations, penalty):
operations = 0
for num in nums:
if num > penalty:
operations += (num - 1) // penalty
if operations > max_operations:
return False
return True
def minimum_penalty(nums, max_operations):
left, right = 1, max(nums)
while left < right:
mid = (left + right) // 2
if can_achieve_penalty(nums, max_operations, mid):
right = mid
else:
left = mid + 1
return left
# Example usage:
print(minimum_penalty([9], 2)) # Output: 3import java.util.*;
public class MinimumPenalty {
private static boolean canAchievePenalty(int[] nums, int maxOperations, int penalty) {
int operations = 0;
for (int num : nums) {
if (num > penalty) {
operations += (num - 1) / penalty;
}
if (operations > maxOperations) {
return false;
}
}
return true;
}
public static int minimumPenalty(int[] nums, int maxOperations) {
int left = 1, right = 1000000000;
while (left < right) {
int mid = left + (right - left) / 2;
if (canAchievePenalty(nums, maxOperations, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
public static void main(String[] args) {
int[] nums = {9};
int maxOperations = 2;
System.out.println(minimumPenalty(nums, maxOperations)); // Output: 3
}
}#include <vector>
#include <iostream>
using namespace std;
bool canAchievePenalty(const vector<int>& nums, int maxOperations, int penalty) {
int operations = 0;
for (int num : nums) {
if (num > penalty) {
operations += (num - 1) / penalty;
}
if (operations > maxOperations) {
return false;
}
}
return true;
}
int minimumPenalty(vector<int>& nums, int maxOperations) {
int left = 1, right = 1e9;
while (left < right) {
int mid = left + (right - left) / 2;
if (canAchievePenalty(nums, maxOperations, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
int main() {
vector<int> nums = {9};
int maxOperations = 2;
cout << minimumPenalty(nums, maxOperations) << endl; // Output: 3
return 0;
}function canAchievePenalty(nums, maxOperations, penalty) {
let operations = 0;
for (let num of nums) {
if (num > penalty) {
operations += Math.floor((num - 1) / penalty);
}
if (operations > maxOperations) {
return false;
}
}
return true;
}
function minimumPenalty(nums, maxOperations) {
let left = 1, right = Math.max(...nums);
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (canAchievePenalty(nums, maxOperations, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
console.log(minimumPenalty([9], 2)); // Output: 3#include <stdio.h>
int canAchievePenalty(int* nums, int numsSize, int maxOperations, int penalty) {
int operations = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] > penalty) {
operations += (nums[i] - 1) / penalty;
}
if (operations > maxOperations) {
return 0;
}
}
return 1;
}
int minimumPenalty(int* nums, int numsSize, int maxOperations) {
int left = 1, right = 1000000000;
while (left < right) {
int mid = left + (right - left) / 2;
if (canAchievePenalty(nums, numsSize, maxOperations, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
int main() {
int nums[] = {9};
int maxOperations = 2;
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", minimumPenalty(nums, size, maxOperations)); // Output: 3
return 0;
}using System;
public class Solution {
private bool CanAchievePenalty(int[] nums, int maxOperations, int penalty) {
int operations = 0;
foreach (int num in nums) {
if (num > penalty) {
operations += (num - 1) / penalty;
}
if (operations > maxOperations) {
return false;
}
}
return true;
}
public int MinimumPenalty(int[] nums, int maxOperations) {
int left = 1, right = 1000000000;
while (left < right) {
int mid = left + (right - left) / 2;
if (CanAchievePenalty(nums, maxOperations, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
public static void Main() {
var sol = new Solution();
Console.WriteLine(sol.MinimumPenalty(new int[]{9}, 2)); // Output: 3
}
}The Python version utilizes a binary search within the interval [1, maximum number of balls], trying to minimize the penalty. The auxiliary function can_achieve_penalty checks if it is feasible to redistribute the balls to satisfy the mid penalty limit.
Time Complexity: O(n log(max(nums)))
Space Complexity: O(1)
Approach 2: Greedy Approach with Priority Queue
Another approach is to continuously divide the largest bags using a priority queue to keep track of the largest bag sizes. By always splitting the largest bag first, we aim to reduce the penalty faster. This works similarly to the binary search approach in terms of dividing the problem space but uses a different method to handle priorities.
import heapq
def minimum_penalty(nums, max_operations):
pq = [-x for x in nums]
heapq.heapify(pq)
while max_operations > 0:
largest = -heapq.heappop(pq)
split = (largest + 1) // 2
heapq.heappush(pq, -split)
heapq.heappush(pq, -(largest - split))
max_operations -= 1
return -pq[0]
# Example usage:
print(minimum_penalty([9], 2)) # Output: 3import java.util.*;
public class MinimumPenalty {
public static int minimumPenalty(int[] nums, int maxOperations) {
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
for (int num : nums) {
pq.add(num);
}
while (maxOperations > 0) {
int largest = pq.poll();
int split = (largest + 1) / 2;
pq.add(split);
pq.add(largest - split);
--maxOperations;
}
return pq.peek();
}
public static void main(String[] args) {
int[] nums = {9};
int maxOperations = 2;
System.out.println(minimumPenalty(nums, maxOperations)); // Output: 3
}
}#include <vector>
#include <queue>
#include <iostream>
using namespace std;
int minimumPenalty(vector<int>& nums, int maxOperations) {
priority_queue<int> pq(nums.begin(), nums.end());
while (maxOperations > 0) {
int largest = pq.top();
pq.pop();
int split = (largest + 1) / 2;
pq.push(split);
pq.push(largest - split);
--maxOperations;
}
return pq.top();
}
int main() {
vector<int> nums = {9};
int maxOperations = 2;
cout << minimumPenalty(nums, maxOperations) << endl; // Output: 3
return 0;
}function minimumPenalty(nums, maxOperations) {
let heap = new MaxHeap(nums);
while (maxOperations > 0) {
const largest = heap.extractMax();
const split = Math.floor((largest + 1) / 2);
heap.insert(split);
heap.insert(largest - split);
maxOperations--;
}
return heap.findMax();
}
class MaxHeap {
constructor(data) {
this.data = data;
this.buildHeap();
}
buildHeap() {
for (let i = Math.floor(this.size() / 2) - 1; i >= 0; i--) {
this.siftDown(i);
}
}
siftDown(index) {
const left = 2 * index + 1;
const right = 2 * index + 2;
let largest = index;
if (left < this.size() && this.data[left] > this.data[largest]) {
largest = left;
}
if (right < this.size() && this.data[right] > this.data[largest]) {
largest = right;
}
if (largest !== index) {
[this.data[largest], this.data[index]] = [this.data[index], this.data[largest]];
this.siftDown(largest);
}
}
insert(value) {
this.data.push(value);
this.siftUp(this.size() - 1);
}
siftUp(index) {
let parent = Math.floor((index - 1) / 2);
while (index > 0 && this.data[parent] < this.data[index]) {
[this.data[parent], this.data[index]] = [this.data[index], this.data[parent]];
index = parent;
parent = Math.floor((index - 1) / 2);
}
}
extractMax() {
if (this.size() === 0) return null;
const root = this.data[0];
this.data[0] = this.data.pop();
this.siftDown(0);
return root;
}
findMax() {
return this.data[0];
}
size() {
return this.data.length;
}
}
console.log(minimumPenalty([9], 2)); // Output: 3#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int *)b) - (*(int *)a);
}
int minimumPenalty(int* nums, int numsSize, int maxOperations) {
qsort(nums, numsSize, sizeof(int), compare);
int low = 1, high = nums[0];
while (low < high) {
int mid = (low + high) / 2;
int operations = 0;
for (int i = 0; i < numsSize && nums[i] > mid; ++i) {
operations += (nums[i] - 1) / mid;
}
if (operations <= maxOperations) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
}
int main() {
int nums[] = {9};
int maxOperations = 2;
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", minimumPenalty(nums, size, maxOperations)); // Output: 3
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int MinimumPenalty(int[] nums, int maxOperations) {
var pq = new SortedSet<(int value, int index)>(Comparer<(int, int)>.Create((a, b) =>
a.value == b.value ? a.index.CompareTo(b.index) : b.value.CompareTo(a.value)));
int index = 0;
foreach (var num in nums) {
pq.Add((num, index++));
}
while (maxOperations > 0 && pq.Max.value > 1) {
var largest = pq.Max;
pq.Remove(largest);
int split = (largest.value + 1) / 2;
pq.Add((split, index++));
pq.Add((largest.value - split, index++));
--maxOperations;
}
return pq.Max.value;
}
public static void Main() {
var sol = new Solution();
Console.WriteLine(sol.MinimumPenalty(new int[]{9}, 2)); // Output: 3
}
}The Python solution employs the heapq module to simulate a max-heap by pushing negative values. This allows for always splitting the currently largest size into smaller sizes efficiently.
Time Complexity: O(maxOperations * log n)
Space Complexity: O(n)
Approach 3: Binary Search
This problem requires us to minimize the cost, which is the maximum number of balls in a single bag. As the maximum value increases, the number of operations decreases, making it easier to meet the condition.
Therefore, we can use binary search to enumerate the maximum number of balls in a single bag and determine if it can be achieved within maxOperations operations.
Specifically, we define the left boundary of the binary search as l = 1 and the right boundary as r = max(nums). Then we continuously perform binary search on the middle value mid = \frac{l + r}{2}. For each mid, we calculate the number of operations needed. If the number of operations is less than or equal to maxOperations, it means mid meets the condition, and we update the right boundary r to mid. Otherwise, we update the left boundary l to mid + 1.
Finally, we return the left boundary l.
The time complexity is O(n times log M), where n and M are the length and the maximum value of the array nums, respectively. The space complexity is O(1).
function minimumSize(nums: number[], maxOperations: number): number {
let [l, r] = [1, Math.max(...nums)];
while (l < r) {
const mid = (l + r) >> 1;
const s = nums.map(x => ((x - 1) / mid) | 0).reduce((a, b) => a + b);
if (s <= maxOperations) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}func minimumSize(nums []int, maxOperations int) int {
r := slices.Max(nums)
return 1 + sort.Search(r, func(mx int) bool {
mx++
s := 0
for _, x := range nums {
s += (x - 1) / mx
}
return s <= maxOperations
})
}impl Solution {
pub fn minimum_size(nums: Vec<i32>, max_operations: i32) -> i32 {
let mut l = 1;
let mut r = *nums.iter().max().unwrap();
while l < r {
let mid = (l + r) / 2;
let mut s: i64 = 0;
for &x in &nums {
s += ((x - 1) / mid) as i64;
}
if s <= max_operations as i64 {
r = mid;
} else {
l = mid + 1;
}
}
l
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Binary Search on Penalty | Time Complexity: O(n log(max(nums))) |
| Greedy Approach with Priority Queue | Time Complexity: O(maxOperations * log n) |
| Binary Search | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Minimum Limit of Balls in a Bag easy or hard?
Minimum Limit of Balls in a Bag is rated Medium on LeetCode. The challenge comes from recognizing that the problem requires binary search on the answer rather than direct simulation of operations.
Minimum Limit of Balls in a Bag Python/Java solution
Most implementations follow the binary search strategy. In Python or Java, set the search range from 1 to max(nums), compute required operations for each midpoint, and adjust the search bounds until the minimum feasible penalty is found.
How to solve Minimum Limit of Balls in a Bag in O(n log m)?
Binary search the minimum possible penalty between 1 and the maximum value in the array. For a candidate penalty p, calculate splits required for each bag using (x - 1) / p. If the total operations stay within maxOperations, the penalty is feasible and you search smaller values.
What is the best approach for Minimum Limit of Balls in a Bag?
Binary Search on Penalty is the optimal approach. Instead of simulating every split, treat the answer as the maximum allowed balls per bag and binary search that value. For each candidate penalty, compute required splits using (x - 1) / p across the array. This yields O(n log m) time where m is the maximum bag size.
Is Minimum Limit of Balls in a Bag asked at Google/Amazon/Meta?
Binary search optimization problems like this commonly appear in interviews at companies such as Amazon, Google, and Meta. Variants involving minimizing the maximum value after limited operations are frequently used to test binary search on answer space.
What data structure is used in Minimum Limit of Balls in a Bag?
The optimal solution primarily uses binary search over integers and simple array iteration. An alternative solution uses a max-heap (priority queue) to repeatedly split the largest bag.
What is the time complexity of Minimum Limit of Balls in a Bag?
The optimal binary search solution runs in O(n log m) time and O(1) space, where n is the number of bags and m is the largest bag size. Each binary search step scans the array once to count required operations.