Minimized Maximum of Products Distributed to Any Store - Solution & Explanation

Problem Overview: You are given n stores and an array quantities where each value represents the number of products of a specific type. Products of the same type must be distributed to stores, and a store can only receive one product type. The goal is to minimize the maximum number of products assigned to any store.

Approach 1: Binary Search over the Maximum Products (Time: O(m log M), Space: O(1))

This problem becomes easier if you think in terms of the answer rather than the distribution. Instead of trying to assign products directly, you search for the smallest possible value x such that no store receives more than x products. This value must lie between 1 and max(quantities). Use binary search over this range.

For a candidate value x, check if the distribution is feasible. For each quantity q, compute how many stores are required if each store can hold at most x items: ceil(q / x). Sum these values across all product types. If the total required stores is ≤ n, the candidate maximum is feasible, so try a smaller value. Otherwise increase the bound. This feasibility check is a simple greedy count and runs in linear time over the array.

The key insight: the feasibility condition is monotonic. If a maximum value x works, any larger value will also work. That monotonic property makes binary search the natural tool here. The algorithm scans the array each iteration, giving total complexity O(m log M), where m is the number of product types and M is the maximum quantity.

Approach 2: Greedy Check with Priority Allocation (Time: O(m log n), Space: O(m))

Another perspective is to repeatedly split the largest product loads across stores using a greedy strategy. Start by placing each product type into a max heap with its quantity. Each heap entry tracks the current maximum load per store for that product type based on how many stores it has been split across.

Iteratively assign additional stores to the product type with the largest current load. Each split reduces the maximum load for that product type because the quantity is divided among more stores. Use a priority queue to always process the largest current load first. This method resembles greedy load balancing and relies on a greedy decision at every step.

While intuitive, this approach is less common in interviews because it requires careful heap bookkeeping and slightly higher overhead. However, it still works efficiently and illustrates the idea of progressively balancing the distribution.

Recommended for interviews: Binary search on the answer with a greedy feasibility check. Interviewers expect you to recognize the monotonic constraint and apply binary search to minimize the maximum load. Mentioning a direct greedy distribution first shows problem exploration, but implementing the binary search solution demonstrates stronger algorithmic judgment.