{x}
blog image

Minimized Maximum of Products Distributed to Any Store

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:

  • A store can only be given at most one product type but can be given any amount of it.
  • After distribution, each store will have been given some number of products (possibly 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.length
  • 1 <= m <= n <= 105
  • 1 <= quantities[i] <= 105

Solution Explanation

This problem asks to find the minimum possible maximum number of products given to any store after distributing all products to n stores, given the quantities of each product type in the quantities array. The solution uses binary search to efficiently find this minimum value.

Core Idea:

The problem can be solved using binary search because of the monotonicity involved. If a certain maximum number of products per store (x) is feasible (all products can be distributed without exceeding x products in any store), then any larger value of x is also feasible. Conversely, if x is infeasible, any smaller value of x will also be infeasible. This property allows for efficient searching using binary search.

Algorithm:

  1. Binary Search Space: The search space is from 1 (minimum possible product per store) to the maximum quantity among all product types (maximum possible product per store).

  2. Check Function (check(x)): This function determines if a given x (maximum products per store) is feasible. It iterates through the quantities array. For each product type, it calculates the number of stores needed to distribute that product type, ensuring that no store gets more than x products. The ceiling division (v + x - 1) // x is crucial here; it calculates the number of stores required for each product type, rounding up if necessary. Finally, it checks if the total number of stores needed (sum(...)) is less than or equal to n. If it is, x is feasible and the function returns True; otherwise, it returns False.

  3. Binary Search Iteration: The while loop implements a binary search. It repeatedly checks the feasibility of the middle value (mid) in the search space. If mid is feasible, the search space is narrowed to the lower half (right = mid); otherwise, it's narrowed to the upper half (left = mid + 1).

  4. Result: The loop continues until left and right converge, at which point left (or right) holds the minimum feasible x. This is the result returned by the function.

Time Complexity Analysis:

  • The binary search takes O(log M) iterations, where M is the range of the search space (approximately the maximum quantity).
  • The check(x) function iterates through the quantities array once in each iteration of the binary search, taking O(m) time, where m is the number of product types.
  • Therefore, the overall time complexity is O(m * log M). Since M is usually much smaller than n, we can simplify it to O(m log(max(quantities))).

Space Complexity Analysis:

The space complexity is O(1) because only a constant amount of extra space is used (variables left, right, mid, cnt).

Example Walkthrough (Python):

Let's consider the example: n = 6, quantities = [11, 6].

The search space initially is [1, 11].

  1. mid = 6: check(6): (11+5)//6 + (6+5)//6 = 3 + 2 = 5 <= 6. Feasible. right = 6.
  2. mid = 3: check(3): (11+2)//3 + (6+2)//3 = 5 + 3 = 8 > 6. Infeasible. left = 4.
  3. mid = 4: check(4): (11+3)//4 + (6+3)//4 = 4 + 3 = 7 > 6. Infeasible. left = 5.
  4. mid = 5: check(5): (11+4)//5 + (6+4)//5 = 4 + 2 = 6 <= 6. Feasible. right = 5.

The loop terminates, and left (or right) is 5. However, the code adds 1 to the final answer due to the way the bisect_left function (or equivalent) is used in finding the first index that satisfies the condition in binary search. Therefore, the final answer is 3.

The provided codes in different languages implement this binary search algorithm with slight variations in syntax. They all achieve the same outcome with the same time and space complexities.