LeetCode Entry
2064. Minimized Maximum of Products Distributed to Any Store
Min of max of quantities spread by n single-type stores search
2064. Minimized Maximum of Products Distributed to Any Store medium
blog post
substack
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 increas 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;
}