2064. Minimized Maximum of Products Distributed to Any Store
Problem Description
The problem presents a scenario where there is a given number of specialty retail stores, denoted by an integer n
, and a certain number of product types, denoted by an array quantities
where each entry quantities[i]
represents the amount available for the i-th
product type. The objective is to distribute these products to the stores following certain rules:
- Each store can receive at most one product type.
- A store can receive any amount of the one product type it is given.
- The goal is to minimize the maximum number of products given to any single store.
This situation is akin to finding the most balanced way of distributing products such that the store with the largest stock has as little product as possible, in order to minimize potential waste or overstock.
In simple terms, you are asked to find the smallest number x
which represents the maximum number of products that any store will have after the distribution is completed.
Intuition
The solution involves using a binary search algorithm. The key insight here is that if we can determine a minimum possible x
such that all products can be distributed without exceeding x
products in any store, we have our answer.
Here's the reasoning process:
- We know that the value of
x
must be between 1 (if there's at least one store for each product) and the maximum quantity inquantities
(if there's only one store). - Using binary search, we can quickly narrow down the range to find the smallest possible
x
. - To test if a given
x
is valid, we check if all products can be distributed to stores without any store getting more thanx
products. This is done by calculating the number of stores needed for each product type (rounded up) and ensuring the sum does not exceedn
.
The check
function in the provided code snippet helps with this validation by returning True
if a given x
allows for all the products to be distributed within the n
stores.
The Python bisect_left
function is used to perform the binary search efficiently. It returns the index of the first element in the given range that matches True
when passed to the check
function. This means it effectively finds the lowest number x
such that check(x)
is true, which is our desired minimum possible maximum number of products per store (x
).
By starting the binary search at 1
and going up to 10**6
(an arbitrary high number to ensure the maximum quantity is covered), we guarantee finding the minimum x
within the valid range.
Learn more about Binary Search patterns.
Solution Approach
The solution adopts a binary search algorithm to efficiently find the minimum value of x
that satisfies the distribution conditions. Binary search is an optimal choice here because it allows for a significant reduction in the number of guesses needed compared to linear search, especially when there's a large range of possible values for x
.
Here is the step-by-step implementation of the solution:
-
Binary Search Algorithm:
- The binary search is used to find the minimum
x
such that all products can be distributed according to the rules. It is efficient because it repeatedly divides the search interval in half. - In this case, the lower and upper bounds for the search are
1
and10**6
respectively. The upper bound is a sufficiently large number to cover the maximum possible quantity.
- The binary search is used to find the minimum
-
Helper Function (
check
):- A helper function,
check
, is used during the binary search to validate whether a givenx
can be used to distribute all the products within the available stores. - For each product type in
quantities
, the function calculates the number of stores required by dividing the quantity of that product type byx
and rounding up (since we can't have a fraction of a store). This is done using(v + x - 1) // x
for eachv
inquantities
. The rounding up is achieved by addingx - 1
before performing integer division.
- A helper function,
-
Using
bisect_left
:- The Python function
bisect_left
from thebisect
module is employed to perform the binary search. The function takes in a range, a target value (True
in this case, ascheck
returns a boolean), and a key function (check
). The key function is called with each mid-value during the search to determine ifx
is too high or too low. bisect_left
will find the positioni
to insert the target value (True
) in the range in order to maintain the sorted order. Since the key function effectively turns the range into a sorted boolean array (False
for values below our target andTrue
for values at or above it), the positioni
represents the smallestx
for whichcheck(x)
isTrue
.
- The Python function
-
Outcome:
- The value of
x
found by thebisect_left
search is incremented by 1 because the range is 0-indexed, whereas the quantities need to be 1-indexed (sincex
can't be zero).
- The value of
This approach of binary search combined with a check for the validity of the distribution ensures that the solution is both efficient and correct, taking O(log M * N)
time complexity, where M
is the range of possible values for x
and N
is the length of quantities
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider an example where we have n = 2
specialty retail stores and quantities = [3, 6, 14]
for the product types.
-
Binary Search Initialization:
- The possible values for
x
start with a lower bound of1
, and an upper bound of10**6
.
- The possible values for
-
First Mid-point Check:
- Let's pick a mid-point for
x
during the binary search. Since our bounds are1
and10**6
, a computationally reasonable mid-point to start could be500,000
. However, for the sake of example, we'll use5
as it's a more illustrative number. - We run the
check
function withx = 5
. We need one store for the first product type (3/5 rounded up is still 1 store), two stores for the second product type (6/5 rounded up is 2 stores), and three stores for the third product type (14/5 rounded up is 3 stores). - In total, we would need
1 + 2 + 3 = 6
stores to distribute the products with each store receiving no more than 5 products. However, we only have2
stores. - Since we can't distribute the products without exceeding
5
products in any store with only2
stores,check(5)
returnsFalse
.
- Let's pick a mid-point for
-
Adjusting the Search Range:
- Since
5
is too small, we adjust our search range. The next mid-point we check is halfway between5
and10**6
, but again as this is an example, we choose7
. - We run the
check
function withx = 7
. This time we would need1
store for the first product type (3/7 rounded up is still 1 store),1
store for the second product type (6/7 rounded up is still 1 store), and2
stores for the third product type (14/7 is exactly 2 stores), totaling1 + 1 + 2 = 4
stores. This is still more than2
stores, socheck(7)
returnsFalse
.
- Since
-
Finding the Valid
x
:- Continuing the binary search, let's try
x = 10
. - Running
check(10)
, the first product type requires1
store (3/10 rounded up is still 1 store), the second product type also requires1
store (6/10 rounded up is still 1 store), and the third product type requires2
stores (14/10 rounded up is 2 stores). The total is1 + 1 + 2 = 4
stores, which is still too many. - However, if we check
x = 15
, we see that each product type would only require1
store: (3/15, 6/15, 14/15 all round up to 1 since we can't have a fraction of a store). The total is3
stores, which is still more than2
, socheck(15)
returnsFalse
.
- Continuing the binary search, let's try
-
Binary Search Conclusion:
- Finally, we try
x = 20
. - Now running
check(20)
, each product type will require only1
store: (3/20, 6/20, 14/20 all round up to 1). The sum is exactly2
stores, which matchesn = 2
. - Since
check(20)
returnsTrue
and we cannot go lower than20
without needing more stores than we have,20
is our smallest possiblex
.
- Finally, we try
In practice, the binary search would proceed by narrowing down the range between the values where check
returns False
and where check
returns True
. In our manually stepped-through example, x = 20
is the solution. This means that we can distribute the products to the 2 stores in such a way that no store has more than 20 products, thereby minimizing the maximum number of products per store.
Solution Implementation
1from bisect import bisect_left
2from typing import List
3
4class Solution:
5 def minimizedMaximum(self, n: int, quantities: List[int]) -> int:
6 # Define a check function that will be used to determine if a specific value of 'x'
7 # allows distributing all the quantities within 'n' stores such that the maximum
8 # quantity in any store does not exceed 'x'.
9 def is_distribution_possible(x):
10 # Calculate the total number of stores required if each store can hold up to 'x'
11 # items. The expression (quantity + x - 1) // x is used to ceiling divide the quantity
12 # by x to find out how many stores are required for each quantity.
13 total_stores_needed = sum((quantity + x - 1) // x for quantity in quantities)
14 # Check if the total number of stores needed does not exceed the available 'n' stores.
15 return total_stores_needed <= n
16
17 # Use binary search (bisect_left) to find the smallest 'x' such that distributing
18 # the items does not exceed the number of stores. We search in the range from 1 to 10**6
19 # as an upper limit, assuming that the maximum quantity per store will not exceed 10**6.
20 # The second argument to bisect_left is 'True' because we are interested in finding the point
21 # where the 'is_distribution_possible' function returns 'True'.
22 min_max_quantity = 1 + bisect_left(range(1, 10**6), True, key=is_distribution_possible)
23
24 # Return the smallest possible maximum quantity that can be put in a store.
25 return min_max_quantity
26
1class Solution {
2 public int minimizedMaximum(int stores, int[] products) {
3 // Initial search space: the lowest possible maximum is 1 (each store can have at least one of any product),
4 // and the highest possible maximum is assumed to be 100000
5 // (based on the problem constraints if given in the problem description).
6 int left = 1, right = 100000;
7
8 // Using binary search to find the minimized maximum value
9 while (left < right) {
10 // Midpoint of the current search space
11 int mid = (left + right) / 2;
12
13 // Counter for the number of stores needed
14 int count = 0;
15
16 // Distribute products among stores
17 for (int quantity : products) {
18 // Each store can take 'mid' amount, calculate how many stores are required
19 // for this particular product, rounding up
20 count += (quantity + mid - 1) / mid;
21 }
22
23 // If we can distribute all products to 'stores' or less with 'mid' maximum product per store,
24 // we are possibly too high in the product capacity (or just right) so we try a lower capacity
25 if (count <= stores) {
26 right = mid;
27 } else {
28 // If we are too low and need more than 'stores' to distribute all products,
29 // we need to increase the product capacity per store
30 left = mid + 1;
31 }
32 }
33
34 // 'left' will be our minimized maximum product per store that fits all products into 'stores' stores.
35 return left;
36 }
37}
38
1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6 // Method to find the minimized maximum number of products per shelf
7 int minimizedMaximum(int n, vector<int>& quantities) {
8 int left = 1; // Start with the minimum possible value per shelf
9 int right = 1e5; // Assume an upper bound for the maximum value per shelf
10
11 // Use binary search
12 while (left < right) {
13 int mid = (left + right) >> 1; // Calculate mid value
14 int count = 0; // Initialize count of shelves needed
15
16 // Iterate through the quantities array
17 for (int& quantity : quantities) {
18 // Calculate and add number of shelves needed for each quantity
19 count += (quantity + mid - 1) / mid;
20 }
21
22 // If the count of shelves needed is less than or equal to the available shelves
23 // there might be a solution with a smaller max quantity, search left side
24 if (count <= n) {
25 right = mid;
26 }
27 // Otherwise, search the right side with larger quantities
28 else {
29 left = mid + 1;
30 }
31 }
32 // When left meets right, it's the minimized max quantity per shelf
33 return left;
34 }
35};
36
1function minimizedMaximum(stores: number, products: number[]): number {
2 // Define the search interval with a sensible start and end.
3 let searchStart = 1;
4 let searchEnd = 1e5; // Assuming 1e5 is the maximum possible quantity.
5
6 // Binary search to find the minimized maximum number of products per store.
7 while (searchStart < searchEnd) {
8 // Calculate the middle value of the current search interval.
9 const middle = Math.floor((searchStart + searchEnd) / 2);
10
11 // Counter to keep track of the total number of stores needed.
12 let storeCount = 0;
13
14 // Iterating over each product quantity to distribute among stores.
15 for (const quantity of products) {
16 // Increment the store count by the number of stores needed for this product.
17 // We take the ceiling to account for incomplete partitions.
18 storeCount += Math.ceil(quantity / middle);
19 }
20
21 // If the store count fits within the number of available stores,
22 // we proceed to check if there's an even smaller maximum.
23 if (storeCount <= stores) {
24 searchEnd = middle;
25 } else {
26 // Else we need to increase the number of products per store and keep looking.
27 searchStart = middle + 1;
28 }
29 }
30
31 // The minimized maximum number of products per store that will fit.
32 return searchStart;
33}
34
Time and Space Complexity
The given Python code aims to find a value of x
that, when used to distribute the quantities of items amongst n
stores, results in a minimized maximum number within a store while ensuring all quantities are distributed. This is achieved by using a binary search via bisect_left
on a range of possible values for x
.
Time Complexity:
The binary search is performed on a range from 1
to a constant value (10**6
), resulting in O(log(C))
complexity, where C
is the upper limit of the search range. Inside the check
function, there is a loop which computes the sum with complexity O(Q)
for each check, where Q
is the length of the quantities
list. Therefore, the time complexity of the entire algorithm is O(Q * log(C))
.
Space Complexity:
The code uses a constant amount of additional memory outside of the quantities
list input. The check
function computes the sum using the values in quantities
without additional data storage that depends on the size of quantities
or the range of values. Hence, the space complexity is O(1)
, as no significant additional space is consumed in relation to the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the output of running the following function using the following tree as input?
1def serialize(root):
2 res = []
3 def dfs(root):
4 if not root:
5 res.append('x')
6 return
7 res.append(root.val)
8 dfs(root.left)
9 dfs(root.right)
10 dfs(root)
11 return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4 StringJoiner res = new StringJoiner(" ");
5 serializeDFS(root, res);
6 return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10 if (root == null) {
11 result.add("x");
12 return;
13 }
14 result.add(Integer.toString(root.val));
15 serializeDFS(root.left, result);
16 serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2 let res = [];
3 serialize_dfs(root, res);
4 return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8 if (!root) {
9 res.push("x");
10 return;
11 }
12 res.push(root.val);
13 serialize_dfs(root.left, res);
14 serialize_dfs(root.right, res);
15}
16
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!