2064. Minimized Maximum of Products Distributed to Any Store

MediumArrayBinary Search
Leetcode Link

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 in quantities (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 than x products. This is done by calculating the number of stores needed for each product type (rounded up) and ensuring the sum does not exceed n.

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

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

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:

  1. 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 and 10**6 respectively. The upper bound is a sufficiently large number to cover the maximum possible quantity.

  2. Helper Function (check):

    • A helper function, check, is used during the binary search to validate whether a given x 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 by x and rounding up (since we can't have a fraction of a store). This is done using (v + x - 1) // x for each v in quantities. The rounding up is achieved by adding x - 1 before performing integer division.

  3. Using bisect_left:

    • The Python function bisect_left from the bisect module is employed to perform the binary search. The function takes in a range, a target value (True in this case, as check returns a boolean), and a key function (check). The key function is called with each mid-value during the search to determine if x is too high or too low.
    • bisect_left will find the position i 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 and True for values at or above it), the position i represents the smallest x for which check(x) is True.

  4. Outcome:

    • The value of x found by the bisect_left search is incremented by 1 because the range is 0-indexed, whereas the quantities need to be 1-indexed (since x can't be zero).

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Example Walkthrough

Let's consider an example where we have n = 2 specialty retail stores and quantities = [3, 6, 14] for the product types.

  1. Binary Search Initialization:

    • The possible values for x start with a lower bound of 1, and an upper bound of 10**6.

  2. First Mid-point Check:

    • Let's pick a mid-point for x during the binary search. Since our bounds are 1 and 10**6, a computationally reasonable mid-point to start could be 500,000. However, for the sake of example, we'll use 5 as it's a more illustrative number.
    • We run the check function with x = 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 have 2 stores.
    • Since we can't distribute the products without exceeding 5 products in any store with only 2 stores, check(5) returns False.

  3. Adjusting the Search Range:

    • Since 5 is too small, we adjust our search range. The next mid-point we check is halfway between 5 and 10**6, but again as this is an example, we choose 7.
    • We run the check function with x = 7. This time we would need 1 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), and 2 stores for the third product type (14/7 is exactly 2 stores), totaling 1 + 1 + 2 = 4 stores. This is still more than 2 stores, so check(7) returns False.

  4. Finding the Valid x:

    • Continuing the binary search, let's try x = 10.
    • Running check(10), the first product type requires 1 store (3/10 rounded up is still 1 store), the second product type also requires 1 store (6/10 rounded up is still 1 store), and the third product type requires 2 stores (14/10 rounded up is 2 stores). The total is 1 + 1 + 2 = 4 stores, which is still too many.
    • However, if we check x = 15, we see that each product type would only require 1 store: (3/15, 6/15, 14/15 all round up to 1 since we can't have a fraction of a store). The total is 3 stores, which is still more than 2, so check(15) returns False.

  5. Binary Search Conclusion:

    • Finally, we try x = 20.
    • Now running check(20), each product type will require only 1 store: (3/20, 6/20, 14/20 all round up to 1). The sum is exactly 2 stores, which matches n = 2.
    • Since check(20) returns True and we cannot go lower than 20 without needing more stores than we have, 20 is our smallest possible x.

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
Not Sure What to Study? Take the 2-min Quiz：

Which of the following shows the order of node visit in a Breadth-first Search?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Recommended Readings

Binary Search Speedrun

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫