# 14.11.2024 [2064. Minimized Maximum of Products Distributed to Any Store]

Min of max of `quantities` spread by `n` single-type stores #medium #binary_search #heap

14.11.2024

2064. Minimized Maximum of Products Distributed to Any Store medium blog post youtube deep-dive

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/800

Problem TLDR

Min of max of quantities spread by n single-type stores #medium #binary_search #heap

Intuition

We can choose the maximum for each store and count how many stores are needed. The number of stores grows linearly with the increase of maximum, so we can do a Binary Search in a space of max = 1..100_000.

Another way of thinking: spread all quantities each on a single store: q1 -> a, q2 -> b, q3 -> c, empty -> d. Then choose peek the type with maximum single value in a store 1 + (quantity - 1)/stores_spread and increase it's spread into one more store. This can be done with a PriorityQueue.

Approach

• let's do greedy-heap solution in Kotlin

• Binary Search in c++

• golf in Rust (it's time is still like a clean Binary Search though)

Complexity

• Time complexity: $$O(mlog(M))$$ for Binary Search, O(nlog(m)) for Heap (slower)

• Space complexity: $$O(1)$$ for Binary Search, O(n) for Heap

Code

    fun minimizedMaximum(n: Int, quantities: IntArray): Int {
        var l = 1; var h = 100000
        while (l <= h) 
            if (n < quantities.sumBy { 1 + (it - 1) / ((l + h) / 2)}) 
            l = (l + h) / 2 + 1 else h = (l + h) / 2 - 1
        return l
    }

    fun minimizedMaximum(n: Int, quantities: IntArray): Int {
        val pq = PriorityQueue<IntArray>(compareBy { -(1 + (it[0] - 1) / it[1]) })
        for (i in 0..<n) pq +=
            if (i < quantities.size) intArrayOf(quantities[i], 1)
            else pq.poll().apply { this[1]++ }
        return 1 + (pq.peek()[0] - 1) / pq.peek()[1]
    }

    pub fn minimized_maximum(n: i32, quantities: Vec<i32>) -> i32 {
        Vec::from_iter(1..100001).partition_point(|x| 
            n < quantities.iter().map(|&q| 1 + (q - 1) / x).sum()) as i32 + 1
    }

    int minimizedMaximum(int n, vector<int>& q) {
        int l = 1, r = 1e5, m, s;
        while (l <= r) {
            s = 0, m = (l + r) / 2;
            for (int x: q) s += (x + m - 1) / m; 
            n < s ? l = m + 1 : r = m - 1;
        }
        return l; 
    }