Minimized Maximum of Products Distributed to Any Store — LeetCode 2064 Python Solution

The problem

You are given an integer n indicating there are n specialty retail stores. There are m product types of varying amounts, which are given as a 0-indexed integer array quantities, where quantities[i] represents the number of products of the ith product type.

Example

Input

n = 6, quantities = [11,6]

Output

3

Explanation

One optimal way is:

Python solution

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)

Complexity

Pattern: Monotonic Stack

Answer "what is the next greater element" for every position in one pass. LeetCode 2064. Minimized Maximum of Products Distributed to Any Store is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.

The monotonic stack guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Related problems