Loading problems...
TL;DR: Use binary search on the answer space to find the smallest maximum capacity per store that allows all products to be distributed within the given store limit.
The problem asks us to distribute types of products, defined by an array quantities, into stores. The rules state that a single store can only carry one type of product, but it can carry any amount of that type. We must distribute every single product. The goal is to minimize the load of the busiest store. Specifically, if is the maximum number of products assigned to any single store, we want to find the minimum possible value of .
This is a classic optimization problem found in interviews, often referred to as "min-max" optimization. The LeetCode 2064 problem, "Minimized Maximum of Products Distributed to Any Store," tests your ability to recognize when a solution space is monotonic and can be searched efficiently.
A naive approach involves checking every possible value for the maximum load , starting from the smallest possible valid load up to the largest possible load.
The smallest possible load is 1 (assuming at least one product exists). The largest possible load occurs if we dump an entire product type into a single store, which would be max(quantities).
The brute force algorithm works as follows:
Pseudo-code:
textmax_val = max(quantities) for x from 1 to max_val: stores_needed = 0 for q in quantities: stores_needed += ceiling(q / x) if stores_needed <= n: return x
Complexity Analysis:
The check function iterates through quantities, taking time. In the worst case, the loop runs max(quantities) times.
The core insight lies in inverting the problem: instead of trying to calculate the optimal distribution directly, we guess a value for the maximum capacity and verify if it is valid.
The Condition Function:
We need a function canDistribute(k) that returns true if it is possible to distribute all products such that no store gets more than items.
To implement this efficiently:
quantities.Visualizing the Search: Imagine the range of possible answers from 1 to (the max quantity).

Consider Example 1: n = 6, quantities = [11, 6].
Initialization:
left = 1right = 11 (max of [11, 6])Iteration 1:
mid = (1 + 11) / 2 = 6.mid is valid. Can we do better? Set right = 6.Iteration 2:
left = 1, right = 6.mid = (1 + 6) / 2 = 3.Iteration 3:
left = 1, right = 3.mid = (1 + 3) / 2 = 2.Termination:
left is 3, right is 3. Loop ends.3.The correctness relies on the invariant maintained by the binary search logic:
[left, right].stores_needed(k) is non-increasing. As capacity increases, the number of stores needed decreases or stays the same.mid is feasible, mid could be the optimal minimum, or the optimal is smaller. By setting right = mid, we ensure we don't discard the potential optimal value.mid is not feasible, mid is strictly too small. The optimal value must be . By setting left = mid + 1, we shrink the search space correctly.cppclass Solution { public: int minimizedMaximum(int n, vector<int>& quantities) { // Search space: from 1 to the max quantity int left = 1; int right = *max_element(quantities.begin(), quantities.end()); while (left < right) { int mid = left + (right - left) / 2; if (canDistribute(n, quantities, mid)) { // If feasible, try a smaller maximum (or stick with current) right = mid; } else { // If not feasible, we need a larger maximum capacity left = mid + 1; } } return left; } private: // Helper function to check if distribution is possible with max capacity 'k' bool canDistribute(int n, const vector<int>& quantities, int k) { int storesNeeded = 0; for (int q : quantities) { // Calculate ceil(q / k) using integer arithmetic storesNeeded += (q + k - 1) / k; // Optimization: Early exit if we exceed available stores if (storesNeeded > n) return false; } return storesNeeded <= n; } };
javaclass Solution { public int minimizedMaximum(int n, int[] quantities) { int left = 1; int right = 0; // Find the maximum quantity to set the upper bound for (int q : quantities) { right = Math.max(right, q); } while (left < right) { int mid = left + (right - left) / 2; if (canDistribute(n, quantities, mid)) { // Mid is a valid max capacity, try to minimize it further right = mid; } else { // Mid is too small, cannot fit products in n stores left = mid + 1; } } return left; } private boolean canDistribute(int n, int[] quantities, int k) { int storesNeeded = 0; for (int q : quantities) { // Equivalent to Math.ceil((double)q / k) storesNeeded += (q + k - 1) / k; if (storesNeeded > n) return false; } return true; } }
pythonimport math class Solution: def minimizedMaximum(self, n: int, quantities: List[int]) -> int: left, right = 1, max(quantities) while left < right: mid = (left + right) // 2 # Check feasibility for capacity 'mid' if self.can_distribute(n, quantities, mid): right = mid else: left = mid + 1 return left def can_distribute(self, n: int, quantities: List[int], k: int) -> bool: stores_needed = 0 for q in quantities: # Calculate ceiling of q / k stores_needed += math.ceil(q / k) if stores_needed > n: return False return True
Let be the length of the quantities array and be the maximum value in quantities.
Time Complexity:
canDistribute check iterates through the quantities array, taking time.The Binary Search on Answer pattern is highly reusable. The following problems share the exact same logic structure: "Minimize the Maximum" or "Maximize the Minimum" with a monotonic condition function.
Why does the naive solution receive a Time Limit Exceeded (TLE)?
max(quantities) and checking each value linearly.mid is valid. Set right = 3.mid is too small. Set left = 2 + 1 = 3.Space Complexity:
In all these cases, we define a search space for the answer and write a greedy helper function to validate a specific candidate value.
Why is my ceiling calculation wrong?
q / k without adjustment.stores_needed is lower than reality, causing the check function to return true incorrectly, leading to an answer that is too small. Use (q + k - 1) / k or Math.ceil.Why does my binary search loop infinitely?
left = mid when left < right.left=3, right=4), mid becomes 3. If the logic sets left = 3, the boundaries never change.left = mid + 1 or right = mid - 1 (or right = mid combined with left < right).Why do I get an Index Out of Bounds error?
quantities).