#2064

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Minimized Maximum of Products Distributed to Any Store

Distribute products to stores so the largest store allocation is minimized using binary search over possible maximums.

Problem Statement

You are given n retail stores and an array quantities of m product types, where quantities[i] represents the number of items of type i. Your task is to distribute all products to the stores so that every product is assigned to some store.

Each store can receive multiple products, but you want to minimize the maximum number of products assigned to any single store. Return the smallest possible maximum number of products per store achievable through optimal distribution.

Examples

Example 1

Input: n = 6, quantities = [11,6]

Output: 3

One optimal way is:

The 11 products of type 0 are distributed to the first four stores in these amounts: 2, 3, 3, 3
The 6 products of type 1 are distributed to the other two stores in these amounts: 3, 3 The maximum number of products given to any store is max(2, 3, 3, 3, 3, 3) = 3.

Example 2

Input: n = 7, quantities = [15,10,10]

Output: 5

One optimal way is:

The 15 products of type 0 are distributed to the first three stores in these amounts: 5, 5, 5
The 10 products of type 1 are distributed to the next two stores in these amounts: 5, 5
The 10 products of type 2 are distributed to the last two stores in these amounts: 5, 5 The maximum number of products given to any store is max(5, 5, 5, 5, 5, 5, 5) = 5.

Example 3

Input: n = 1, quantities = [100000]

Output: 100000

The only optimal way is:

The 100000 products of type 0 are distributed to the only store. The maximum number of products given to any store is max(100000) = 100000.

Constraints

m == quantities.length
1 <= m <= n <= 105
1 <= quantities[i] <= 105

Solution Approach

Binary Search on Maximum Allocation

Set the search range from 1 to the largest quantity. For each candidate maximum x, check if all products can be distributed without exceeding x in any store.

Feasibility Check Using Greedy Division

For each product type, compute how many stores are needed if each store gets at most x products. Sum the required stores and compare to n. If total stores exceed n, x is too small.

Iterate Until Minimum Maximum Found

Adjust the binary search bounds based on feasibility. The lowest x that passes the greedy check is the minimized maximum per store.

Complexity Analysis

Metric	Value
Time	O(m + (n - m)logm)
Space	O(m)

Time complexity is O(m log(maxQuantity)) due to binary search over possible maximums and O(m) check per candidate. Space complexity is O(m) for storing quantities and temporary calculations.

What Interviewers Usually Probe

Look for efficient allocation instead of simulating all permutations.
Consider the monotonic behavior when maximum per store changes.
Expect binary search over the answer rather than direct computation.

Common Pitfalls or Variants

Common pitfalls

Trying to distribute products sequentially without bounding the maximum.
Not accounting for the required number of stores per product type.
Confusing the maximum per store with average allocation.

Follow-up variants

Change the problem to minimize the sum of squares of products per store.
Limit each store to at most k types of products and find the minimized maximum.
Allow splitting products partially, requiring fractional distribution calculations.

FAQ

What is the main idea behind minimizing the maximum products per store?

Use binary search over possible maximums and a greedy approach to check if distribution is feasible for each candidate.

Why does binary search work in this problem?

Because the feasibility of a maximum x is monotonic: if x is too small, it fails; any larger x will succeed.

How do I compute required stores for each product type?

Divide the quantity of each type by the candidate maximum x, rounding up to get the number of stores needed.

Can GhostInterview suggest the actual allocation per store?

It focuses on the minimized maximum value, but the greedy checks also outline how products could be distributed.

Does this problem pattern relate to other binary search over answer problems?

Yes, it exemplifies the 'Binary search over the valid answer space' pattern common in allocation and capacity optimization problems.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

class Solution:
    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:
        def check(x):
            return sum((v + x - 1) // x for v in quantities) <= n

        return 1 + bisect_left(range(1, 10**6), True, key=check)

Continue Practicing

#2071 maximum number of tasks you can assign #2141 maximum running time of n computers #2234 maximum total beauty of the gardens