Problem Statement in English

You’re given an integer n which is the number of stores, and an array quantities where quantities[i] is the number of products in the i-th warehouse. You want to distribute the products to the stores such that the maximum number of products assigned to any store is minimized.

Return the minimum possible maximum number of products that can be assigned to a store.

Approach

I thorughly recommend reading my blog post on 875. Koko Eating Bananas to understand the approach to this problem. It’s the same pattern.

Solution in Python


class Solution:
    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:
        M = len(quantities)

        def good(guess):
            req = 0
            for q in quantities:
                req += ceil(q / guess)

            return req <= n

        l, r = 1, max(quantities)

        while l < r:
            m = (l + r) // 2

            if good(m):
                r = m
            else:
                l = m + 1
        
        return r

Complexity

  • Time: $O(M \log(\max(quantities)))$

  • Space: $O(1)$
    Since we’re using constant space.

Mistakes I Made

I had to read my blog post on 875. Koko Eating Bananas to understand how to approach this pattern. Felt so dumb after reading it 🤦‍♂️

And we are done.