Minimized Maximum of Products Distributed to Any Store Solution
Minimized Maximum of Products Distributed to Any Store solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimized Maximum of Products Distributed to Any Store is a medium coding problem on arrays, greedy and binary search, asked in Amazon, Google and Flipkart interviews.
- Difficulty: Medium
- Topics: Arrays, Greedy, Binary Search
- Asked at: Amazon, Google, Flipkart
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A warehouse ships m product types to n retail stores; quantities[i] is the number of units of type i.
Every unit must be shipped. A store may receive units of at most one product type, in any amount (a store may also receive nothing). Let x be the largest number of units any single store receives.
Return the smallest possible x.
Example 1
Input: n = 6, quantities = [11,6]
Output: 3
Explanation: Split 11 as 3 + 3 + 3 + 2 over four stores and 6 as 3 + 3 over two.
Example 2
Input: n = 7, quantities = [15,10,10]
Output: 5
Explanation: Three stores take 5 each of the first type, two take 5 each of the others.
Example 3
Input: n = 1, quantities = [100000]
Output: 100000
Constraints
m == quantities.length1 <= m <= n <= 10^51 <= quantities[i] <= 10^5
Hints for Minimized Maximum of Products Distributed to Any Store
Hint 1
Fix a cap
xon what one store may hold. How many stores does product typeithen need?Hint 2
It needs
ceil(quantities[i] / x)stores, and the cap is achievable exactly when those counts add up to at mostn.Hint 3
Larger caps never need more stores, so binary-search the smallest feasible
xbetween 1 andmax(quantities).
How to solve Minimized Maximum of Products Distributed to Any Store
Turn the optimisation into a yes/no question: can every product be shipped if no store holds more than x units? The answer flips from no to yes exactly once as x grows, so binary search finds the smallest yes.
Approach
- Search
xin[1, max(quantities)]— the upper end is always feasible becausem <= n. - For a candidate
x, sumceil(q / x)over all types (stop early once the sum passesn). - If the sum is at most
n,xis feasible: move the upper end down tox; otherwise move the lower end tox + 1. - Return the point where the bounds meet.
Why it works
With a cap of x, type i cannot use fewer than ceil(q_i / x) stores and never needs more, and types cannot share stores, so the minimum total is the sum of those ceilings. Increasing x can only shrink each ceiling, which makes feasibility monotone and the binary search exact.
Complexity
- Time —
O(m log Q) with Q = max(quantities) - Space —
O(1)
Pitfalls
- The sum of ceilings at
x = 1can reach 10^10 — stop adding once it exceedsn(or use 64-bit). - Compute
ceil(q / x)as(q + x - 1) / xin integer arithmetic. - Stores left empty are allowed; the condition is
<= n, not== n.
Reference solution
Python
from typing import List
def minimizedMaximum(n: int, quantities: List[int]) -> int:
def feasible(x):
need = 0
for q in quantities:
need += (q + x - 1) // x
if need > n:
return False
return True
lo, hi = 1, max(quantities)
while lo < hi:
mid = (lo + hi) // 2
if feasible(mid):
hi = mid
else:
lo = mid + 1
return loJava
public static int minimizedMaximum(int n, int[] quantities) {
int lo = 1, hi = 0;
for (int q : quantities) hi = Math.max(hi, q);
while (lo < hi) {
int mid = (lo + hi) >>> 1;
int need = 0;
for (int q : quantities) {
need += (q + mid - 1) / mid;
if (need > n) break;
}
if (need <= n) hi = mid; else lo = mid + 1;
}
return lo;
}C++
int minimizedMaximum(int n, vector<int>& quantities) {
int lo = 1, hi = *max_element(quantities.begin(), quantities.end());
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int need = 0;
for (int q : quantities) {
need += (q + mid - 1) / mid;
if (need > n) break;
}
if (need <= n) hi = mid; else lo = mid + 1;
}
return lo;
}JavaScript
var minimizedMaximum = function(n, quantities) {
var feasible = function(x) {
var need = 0;
for (var i = 0; i < quantities.length; i++) {
need += Math.floor((quantities[i] + x - 1) / x);
if (need > n) return false;
}
return true;
};
var lo = 1, hi = 0;
for (var j = 0; j < quantities.length; j++) if (quantities[j] > hi) hi = quantities[j];
while (lo < hi) {
var mid = (lo + hi) >> 1;
if (feasible(mid)) hi = mid; else lo = mid + 1;
}
return lo;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Greedy Algorithms