← DSA Atlas
Dedicated problem page · #2064

Minimized Maximum of Products Distributed to Any Store

MediumBinary SearchBinary search on the answerBinary search on the answer with a feasibility check
Solve on LeetCode ↗
2064
MediumBinary SearchBinary search on the answer with a feasibility checkBinary search on the answer

Minimized Maximum of Products Distributed to Any Store

You have n retail stores and an array quantities where quantities[i] is the number of products of the ith type. Distribute all products so each store receives products of at most one type (a store may receive 0). Let x be the maximum number of products any single store receives. Return the minimum possible value of x.

Open official problem prompt ↗
In plain English

Find the smallest possible value for the busiest store's load, given that every store handles a single product type and only n stores exist.

Picture it like this

You are bottling several flavors of juice into bottles of a fixed capacity, and you only own n bottles. Bigger bottles mean fewer bottles are needed. You want the smallest bottle size such that all the juice still fits in n bottles.

Example
Input
n = 6, quantities = [11, 6]
Output
3
Why
With cap 3, type 11 needs ceil(11/3)=4 stores and type 6 needs ceil(6/3)=2 stores, totaling 6 stores, which fits n=6; no smaller cap fits.
Constraints
m == quantities.length1 <= m <= n <= 10^51 <= quantities[i] <= 10^5
Pattern lesson

See the pattern, then code

Binary search on the answer
Recognition clue

You are asked to minimize a maximum (the peak load per store) subject to a resource limit (n stores). Minimizing a maximum under a monotone feasibility test is the signature of binary search on the answer.

↗
Binary Search

Sorted data or a monotonic true/false condition over a possible answer.. If a per-store cap x works, any larger cap also works, so feasibility is monotone in x. For a fixed cap x, type i needs ceil(quantities[i]/x) stores; the total stores needed decreases as x grows. Binary search for the smallest x whose total store demand is <= n.

New words, made simpleKnow these before the algorithm
Binary search on the answer
Instead of searching an array, you search the numeric range of possible answers and test each candidate with a yes/no feasibility check.
Feasibility check
A function that, given a candidate cap x, decides whether the goal is achievable — here, whether the total stores needed is at most n.
Monotonicity
The property that once a cap works, every larger cap also works, which is what makes binary search valid.
Ceiling division
ceil(q/x), computed as (q + x - 1) // x, gives the number of stores needed to hold q products in chunks of at most x.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Linear scan over caps

With caps up to 10^5 and m up to 10^5, this is up to 10^10 operations — far too slow.

Try every cap x from 1 upward; for each, sum ceil(q/x) and return the first x whose total is <= n.

Time O(m * max(quantities))Space O(1)
Best choiceBinary search on the cap

The feasibility test is monotone in x, so binary search finds the optimum in a handful of passes over the array.

Binary search x in [1, max(quantities)]; test feasibility with the ceil-division sum and keep the smallest feasible x.

Time O(m log(max(quantities)))Space O(1)
The rule we keep true

Invariant

Throughout the loop, the answer lies in the inclusive range [lo, hi]: every cap below lo has been proven infeasible (needs more than n stores) and hi is the smallest cap proven feasible so far.

Why this is correct

Reasoning

The stores needed for a fixed cap x is a non-increasing function of x — a larger cap never needs more stores. Therefore feasibility (stores needed <= n) is monotone: false for small caps, true for large caps, flipping exactly once. Binary search converges on that boundary, which is the minimum feasible cap.

The algorithm in three movesSay these aloud before coding
1Set the search range for the cap x from 1 to max(quantities)

cap=6: 2+1=3 stores <= 6, feasible, hi=6

2For a candidate cap mid, sum ceil(q/mid) over all types to get stores needed

cap=3: 4+2=6 stores <= 6, feasible, hi=3

3If stores needed <= n, the cap is feasible: shrink the upper bound

cap=2: 6+3=9 stores > 6, infeasible, lo=3 -> answer 3

4Otherwise raise the lower bound

5Return the smallest feasible cap

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
110
61
n=62
1 · Readn=6, quantities=[11,6]
2 · AskWhat is the cap range?
3 · Update statelo=1, hi=11
4 · ResultSearch caps 1..11.
Key takeaway

Two product types (11 and 6) must be split across 6 stores; the smallest workable per-store cap is 3.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3Bound the search

    A cap of 1 always works given enough stores, and no cap ever needs to exceed the largest single quantity, so [1, max(quantities)] brackets the answer.

  2. 2
    Lines 4-5Pick the midpoint cap

    Standard lower-bound binary search: mid is the candidate cap being tested this iteration.

  3. 3
    Lines 6Feasibility via ceiling division

    (q + mid - 1) // mid is ceil(q/mid), the stores type q needs at cap mid; summing gives total stores required.

  4. 4
    Lines 7-10Shrink toward the boundary

    If it fits within n stores, mid might be the answer so keep it (hi=mid); otherwise mid is too small, discard it (lo=mid+1).

  5. 5
    Lines 11Return the minimum cap

    When lo==hi the range holds exactly the smallest feasible cap.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • A single product type (m=1): the answer is ceil(quantities[0]/n).
  • n equals m: every store gets one full type, so the answer is max(quantities).
  • n much larger than total products: many stores stay empty and the answer can drop to 1.
  • All quantities equal: the answer still depends on how the shared store budget splits across types.
!

Common beginner mistakes

  • Using floor instead of ceiling division when counting stores per type — floor undercounts and accepts infeasible caps.
  • Starting the low bound at 0, which causes a division-by-zero in the feasibility check.
  • Setting the high bound to sum(quantities) instead of max(quantities); it still works but wastes iterations, and forgetting a cap of 0 is never valid.
  • Returning mid from inside the loop instead of letting lo and hi converge, which can skip the true minimum.
Check your understanding

Why is it safe to cap the binary search's upper bound at max(quantities) rather than the total number of products?

More in Binary Search

#33Search in Rotated Sorted ArrayBinary search on a rotated array#153Find Minimum in Rotated Sorted ArrayBinary search for the rotation point#875Koko Eating BananasBinary search on the answer#4Median of Two Sorted ArraysBinary search on the partition#34Find First and Last Position of ElementLower-bound binary search on both ends#35Search Insert PositionLower-bound binary search