• Leetcode POTDs

Problem 2064 Minimized Maximum of Products Distributed to Any Store

Problem Statement

Link - Problem 2064

Question

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

class Solution {
public:
    int minimizedMaximum(int n, vector<int>& quantities) {
        // Initialize the search range for binary search
        int low = 1, high = INT_MIN, res = 0;

        // Find the maximum quantity in the quantities vector to set the upper bound
        for(int x: quantities)
            if(high < x)
                high = x;

        // Perform binary search to find the minimized maximum value of products per store
        while(low <= high) {
            int mid = low + (high - low) / 2;  // Midpoint to test as a possible max value
            int sum = 0;  // Sum represents the total stores needed if max products per store is `mid`

            // Calculate total number of stores required if max products per store is `mid`
            for(int x: quantities)
                sum += (ceil((float)x / float(mid)));  // Calculate number of stores needed for each product

            // Check if this midpoint allows for distribution within the given store limit `n`
            if(sum <= n) {
                res = mid;   // Update the result with current valid mid
                high = mid - 1;  // Try for a smaller maximum by reducing the upper bound
            } else {
                low = mid + 1;  // Increase the lower bound if more stores are needed than available
            }
        }

        return res;
    }
};

Complexity Analysis

| Algorithm     | Time Complexity           | Space Complexity |
| ------------- | ------------------------- | ---------------- |
| Binary Search | O(m log(max(quantities))) | O(1)             |

Explanation

Intial Thoughts

This problem requires distributing products into stores such that the maximum number of products per store is minimized. Given the constraints of m <= n and 1 <= quantities[i] <= 10^5, a brute force approach would not be feasible. A binary search could potentially work, as the answer should be between the minimum and maximum quantity values. We also need to find the maximum quantity value to determine our upper search bound.

Intuitive Analysis

The problem essentially boils down to a division problem, distributing quantities as evenly as possible. Each iteration of the binary search represents a maximum products per store value. For each quantity, the number of required stores is calculated using ceiling division. If the total required stores are less than or equal to n, we know the answer is less than or equal to the current mid value and we continue searching the lower half. If the total required stores exceed n, we increase the lower bound to find a larger maximum products per store. The iterative approach will eventually converge to the optimal result.

1. Intuition

• The problem can be solved using binary search to find the minimum maximum number of products per store.
• The search range is from 1 to the maximum quantity in the quantities vector.
• The goal is to find the smallest maximum number of products per store that allows distribution within the given store limit n.
• The key insight is to calculate the total number of stores required if the maximum products per store is mid and check if it’s within the limit n.
• If the total number of stores required is less than or equal to n, update the result with the current mid and try to find a smaller maximum.
• If the total number of stores required is more than n, increase the lower bound to try a larger maximum.
• The binary search continues until the lower bound is greater than the upper bound.

2. Implementation

• Initialize the search range with low = 1 and high = INT_MIN, and the result res = 0.
• Find the maximum quantity in the quantities vector to set the upper bound high with for(int x: quantities) if(high < x) high = x;
• Perform binary search with while(low <= high) and calculate the midpoint mid = low + (high - low) / 2;
• Calculate the total number of stores required if the maximum products per store is mid with for(int x: quantities) sum += (ceil((float)x / float(mid)));
• Check if the total number of stores required is within the limit n with if(sum <= n) and update the result accordingly.
• Update the search range with high = mid - 1 if the total number of stores required is within the limit, or low = mid + 1 otherwise.
• Return the result res after the binary search is complete.

Complexity Analysis

Time Complexity:

• Time complexity is analyzed based on the nested loops in the provided code. The outer while loop iterates log(high) times due to the binary search nature, where high is the maximum quantity in the quantities vector.
• Inside the while loop, there’s another for loop that iterates over the quantities vector, adding up to m operations (where m represents the number of elements in quantities).
• Since these two loops are nested, the overall time complexity would be O(m log(max(quantities))) in the worst case scenario, where max(quantities) represents the maximum quantity in the vector, thus influencing the number of iterations of the while loop.

Space Complexity:

• The algorithm uses a constant amount of space to store the low, high, and res variables, contributing O(1) to space complexity.
• Additionally, it makes use of the input vector quantities, but does not create any auxiliary data structures that scale with input size.
• Therefore, the total space complexity remains O(1) as the space used does not grow with input size n or the size of quantities vector.

Footnote

This question is rated as Medium difficulty.

Hints

There exists a monotonic nature such that when x is smaller than some number, there will be no way to distribute, and when x is not smaller than that number, there will always be a way to distribute.

If you are given a number k, where the number of products given to any store does not exceed k, could you determine if all products can be distributed?

Implement a function canDistribute(k), which returns true if you can distribute all products such that any store will not be given more than k products, and returns false if you cannot. Use this function to binary search for the smallest possible k.

Similar Questions: