Minimized Maximum of Products Distributed to Any Store

Medium
1378.

Minimized Maximum of Products Distributed to Any Store

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.

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.length
  • 1 <= m <= n <= 10^5
  • 1 <= quantities[i] <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[]} quantities
 * @return {number}
 */
var minimizedMaximum = function(n, quantities) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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.length
  • 1 <= m <= n <= 10^5
  • 1 <= quantities[i] <= 10^5

Hints for Minimized Maximum of Products Distributed to Any Store

  1. Hint 1

    Fix a cap x on what one store may hold. How many stores does product type i then need?

  2. Hint 2

    It needs ceil(quantities[i] / x) stores, and the cap is achievable exactly when those counts add up to at most n.

  3. Hint 3

    Larger caps never need more stores, so binary-search the smallest feasible x between 1 and max(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

  1. Search x in [1, max(quantities)] — the upper end is always feasible because m <= n.
  2. For a candidate x, sum ceil(q / x) over all types (stop early once the sum passes n).
  3. If the sum is at most n, x is feasible: move the upper end down to x; otherwise move the lower end to x + 1.
  4. 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 = 1 can reach 10^10 — stop adding once it exceeds n (or use 64-bit).
  • Compute ceil(q / x) as (q + x - 1) / x in 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 lo

Java

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