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.
You need to distribute all products to the retail stores following these rules:
0). Let x represent the maximum number of products given to any store. You want x to be as small as possible, i.e., you want to minimize the maximum number of products that are given to any store.Return the minimum possible x.
Example 1:
Input: n = 6, quantities = [11,6] Output: 3 Explanation: 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 Explanation: 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 Explanation: 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.length1 <= m <= n <= 1051 <= quantities[i] <= 105This approach uses binary search to find the minimal possible value of the maximum number of products any store can receive. For each candidate value of maximum products, validate whether the distribution is possible using this value. If distribution is possible, try to lower the maximum; otherwise, increment it.
In this solution, we initialize the binary search range with left being 1 and right as the maximum quantity in the list. For each midpoint, we check if it's possible to distribute all products under this maximum threshold (using ceiling division).
Java
C++
C
C#
JavaScript
Time Complexity: O(m log(max(quantities))), where m is the number of product types.
Space Complexity: O(1), as we only use a fixed amount of extra space.
This approach tries to distribute products product-by-product to the least filled store using a priority queue. The queue handles product allocation dynamically, prioritizing lesser filled stores to balance distribution.
The solution maintains a heap for retail stores initially set to size n with negative ones. For each quantity, the largest product is distributed to the least loaded store/s, maintaining a balanced load across stores.
Java
C++
Time Complexity: O(m log n + n), where m is the number of products and n the number of stores.
Space Complexity: O(n) for maintaining the heap of stores.
| Approach | Complexity |
|---|---|
| Binary Search over the Maximum Products | Time Complexity: O(m log(max(quantities))), where m is the number of product types. |
| Greedy Check with Priority Allocation | Time Complexity: O(m log n + n), where m is the number of products and n the number of stores. |
Minimized Maximum of Products Distributed to Any Store - Leetcode 2064 - Python • NeetCodeIO • 9,188 views views
Watch 9 more video solutions →Practice Minimized Maximum of Products Distributed to Any Store with our built-in code editor and test cases.
Practice on FleetCode