Sponsored
Sponsored
This 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.
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.
1def minimizedMaximum(n, quantities):
2 def canDistribute(max_products):
3 stores_needed = 0
4 for q in quantities:
5 stores_needed += (q + max_products - 1) // max_products
6 return stores_needed <= n
7
8 left, right = 1, max(quantities)
9 while left < right:
10 mid = (left + right) // 2
11 if canDistribute(mid):
12 right = mid
13 else:
14 left = mid + 1
15 return leftIn 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).
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.
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.
1import heapq
2
3def
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.