NeetCode #281LC-2064MediumBinary Search
← Back to All Problems#281 · #2064 · Minimized Maximum of Products Distributed to Any Store(分配给商店的最多商品的最小值)
📌 Problem Statement & Constraints
You are given
n stores and an array quantities where quantities[i] is the number of products of type i. You must distribute all products to the stores, and each store receives products of only one type. Return the minimum possible maximum number of products given to any store. Constraints: 1 <= n <= 10^5, 1 <= m <= 10^5, 1 <= quantities[i] <= 10^5.💡 Core Algorithmic Approaches
- Binary search on the answer
x: "can every store receive at mostxproducts" is monotone inx. - For a given
x, the number of stores needed for typeiisceil(quantities[i] / x), so the total issum(ceil(q / x)). - The answer is feasible when the total is at most
n. Usehi = midto find the smallest feasiblex. - The lower bound is 1 and the upper bound is
max(quantities), since one store can always take a whole type.
💻 Benchmark Python3 Implementation
class Solution:
def minimizedMaximum(self, n: int, quantities: List[int]) -> int:
lo, hi = 1, max(quantities)
while lo < hi:
mid = (lo + hi) // 2
# stores needed if each store takes at most mid products
stores = sum((q + mid - 1) // mid for q in quantities)
if stores <= n:
hi = mid # feasible -> try a smaller cap
else:
lo = mid + 1
return lo⚡ Complexity Deep Dive
⏱️ Time Complexity
O(m log(max(quantities))): each feasibility check is O(m).
💾 Space Complexity
O(1): a few scalars.
⚠️ Interview Pitfalls & Follow-ups
- Using
q // midinstead of the ceiling: integer division truncates, so the store count would be underestimated. - Using
hi = mid - 1when feasible: could skip the optimum. - Assuming products can be split across stores: each store receives only one type, which is why the ceiling division is per type.
- Setting the lower bound to 0: a cap of 0 is infeasible whenever any quantity is positive.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.