Problem

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.

Examples

Example 1:

1
2
3
4
5
6

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:

1
2
3
4
5
6
7

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:

1
2
3
4
5

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.

Solution

Method 1 - Binary Search

We need to distribute products to n stores such that the maximum number of products any store receives, x, is minimized. Here’s how we can approach this problem:

  1. Binary Search: We’ll use binary search to minimize x. The range of x is between 1 (if each store gets at least one product) and the maximum possible value in quantities (in case all products of one type go to one store).

  2. Feasibility Check: For a given x during the binary search, we need to check if it’s feasible to distribute the products such that no store gets more than x products. We can sum the number of stores needed for each product type to ensure it doesn’t exceed n.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
    public int minimizedMaximum(int n, int[] quantities) {
        int left = 1;
        int right = 0;
        for (int q : quantities) {
            right = Math.max(right, q);
        }
        
        int ans = right;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (isFeasible(n, quantities, mid)) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    private boolean isFeasible(int n, int[] quantities, int x) {
        int storesNeeded = 0;
        for (int q : quantities) {
            storesNeeded += (q + x - 1) / x;
        }
        return storesNeeded <= n;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:
        left, right = 1, max(quantities)
        ans = right
        
        while left <= right:
            mid = (left + right) // 2
            if self.is_feasible(n, quantities, mid):
                ans = mid
                right = mid - 1
            else:
                left = mid + 1
                
        return ans
    
    def is_feasible(self, n: int, quantities: List[int], x: int) -> bool:
        stores_needed = 0
        for q in quantities:
            stores_needed += (q + x - 1) // x
        return stores_needed <= n

Complexity

  • ⏰ Time complexity:  O(m log(max(quantities))) where m is the number of product types. This accounts for the binary search over the range and validating each guess which involves a single pass through quantities.
  • 🧺 Space complexity:  O(1) since we’re only using a few additional variables.