Minimized Maximum of Products Distributed to Any Store

medium array binary search greedy

Problem

There are n stores and m product types with counts quantities[i]. Distribute all products so each store gets at most one product type (any amount). Let x be the largest number of products handed to any single store. Return the minimum possible x.

Inputn = 6, quantities = [11, 6]

Output3

Type 0 (11) over 4 stores as 2,3,3,3 and type 1 (6) over 2 stores as 3,3 — six stores, max load 3.

n (stores)

quantities (comma-separated)

def minimizedMaximum(n, quantities):
    def can(k):                         # max k per store?
        stores = 0
        for q in quantities:
            stores += (q + k - 1) // k  # ceil(q / k)
        return stores <= n
    lo, hi = 1, max(quantities)
    while lo < hi:
        mid = (lo + hi) // 2
        if can(mid):
            hi = mid                    # mid works, try smaller
        else:
            lo = mid + 1                # need bigger cap
    return lo

function minimizedMaximum(n, quantities) {
  const can = (k) => {                  // max k per store?
    let stores = 0;
    for (const q of quantities)
      stores += Math.ceil(q / k);       // stores for this type
    return stores <= n;
  };
  let lo = 1, hi = Math.max(...quantities);
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (can(mid)) hi = mid;             // mid works, try smaller
    else lo = mid + 1;                  // need bigger cap
  }
  return lo;
}

class Solution {
    public 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;
            if (can(quantities, n, mid)) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
    private boolean can(int[] quantities, int n, int k) {
        long stores = 0;
        for (int q : quantities) stores += (q + k - 1) / k;
        return stores <= n;
    }
}

class Solution {
public:
    int minimizedMaximum(int n, vector<int>& quantities) {
        int lo = 1, hi = 0;
        for (int q : quantities) hi = max(hi, q);
        auto can = [&](int k) {
            long long stores = 0;
            for (int q : quantities) stores += (q + k - 1) / k;
            return stores <= n;
        };
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (can(mid)) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
};

Explanation

This is a binary search on the answer. We never search inside the array; instead we search over the possible values of x — the cap on how many products any one store may receive — and look for the smallest cap that still lets everything fit.

The answer is monotonic: if a cap k works, then every larger cap also works (more room per store is never worse). That clean cutoff is exactly what binary search needs. The smallest meaningful cap is 1, and the largest we ever need is max(quantities) (give each type its own single store).

The feasibility check can(k) is a greedy count. With a cap of k, product type i needs ceil(quantities[i] / k) stores. Summing that over all types gives the total stores required; if that sum is ≤ n, the cap is feasible.

If can(mid) is true we tighten with hi = mid; otherwise the cap is too small, so lo = mid + 1. When lo meets hi, that value is the minimum possible x.

Example: n = 6, quantities = [11, 6]. Cap 3 needs ceil(11/3) + ceil(6/3) = 4 + 2 = 6 stores — exactly n — while cap 2 needs 6 + 3 = 9 > 6. So the answer is 3.

Time: O(m log(max q)) Space: O(1)