Minimized Maximum of Products Distributed to Any Store solution and explanation
Google
9 more videos on this problem
Minimized Maximum of Products Distributed to Any Store - Leetcode 2064 - PythonNeetCodeIO · 12:49 · 10K views
Minimized Maximum of Products Distributed to Any Store | Leetcode 2064 | codestorywithMIKcodestorywithMIK · 25:39 · 10K views
Minimized Maximum of Products Distributed to Any Store | Leetcode 2064Techdose · 19:41 · 4K views
2064. Minimized Maximum of Products Distributed to Any Store | Binary Search | Greedy | 2 ApproachesAryan Mittal · 19:52 · 1K views
2064. Minimized Maximum of Products Distributed to Any Store | Leetcode Weekly Contest 266 | DSATejpratap Pandey · 17:29 · 1K views
2064. Minimized Maximum of Products Distributed to Any Store (Leetcode Medium)Programming Live with Larry · 14:02 · 1K views
LeetCode 2064. Minimized Maximum of Products Distributed to Any Store | PythonLea's coding · 5:05 · 569 views
LeetCode 2064. Minimized Maximum of Products Distributed to Any Store | Binary Search Part 4Base Case · 7:50 · 423 views
Leetcode - 2064. Minimized Maximum of Products Distributed to Any Store | Binary Search on answerRaman Bhari · 34:41 · 354 views
LeetCode 2064 Minimized Maximum of Products Distributed to Any Store | Binary Search| Google AmazonCode Harmony · 21:20 · 242 views
The problem
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). Letxrepresent the maximum number of products given to any store. You wantxto 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.length1 <= m <= n <= 1051 <= quantities[i] <= 105
Approach overview
Problem Overview: You are given n stores and an array quantities where each value represents the number of products of a specific type. Products of the same type must be distributed to stores, and a store can only receive one product type. The goal is to minimize the maximum number of products assigned to any store.
Approach 1: Binary Search over the Maximum Products (Time: O(m log M), Space: O(1))
This problem becomes easier if you think in terms of the answer rather than the distribution. Instead of trying to assign products directly, you search for the smallest possible value x such that no store receives more than x products. This value must lie between 1 and max(quantities). Use binary search over this range.
For a candidate value x, check if the distribution is feasible. For each quantity q, compute how many stores are required if each store can hold at most x items: ceil(q / x). Sum these values across all product types. If the total required stores is ≤ n, the candidate maximum is feasible, so try a smaller value. Otherwise increase the bound. This feasibility check is a simple greedy count and runs in linear time over the array.
The key insight: the feasibility condition is monotonic. If a maximum value x works, any larger value will also work. That monotonic property makes binary search the natural tool here. The algorithm scans the array each iteration, giving total complexity O(m log M), where m is the number of product types and M is the maximum quantity.
Approach 2: Greedy Check with Priority Allocation (Time: O(m log n), Space: O(m))
Another perspective is to repeatedly split the largest product loads across stores using a greedy strategy. Start by placing each product type into a max heap with its quantity. Each heap entry tracks the current maximum load per store for that product type based on how many stores it has been split across.
Iteratively assign additional stores to the product type with the largest current load. Each split reduces the maximum load for that product type because the quantity is divided among more stores. Use a priority queue to always process the largest current load first. This method resembles greedy load balancing and relies on a greedy decision at every step.
While intuitive, this approach is less common in interviews because it requires careful heap bookkeeping and slightly higher overhead. However, it still works efficiently and illustrates the idea of progressively balancing the distribution.
Recommended for interviews: Binary search on the answer with a greedy feasibility check. Interviewers expect you to recognize the monotonic constraint and apply binary search to minimize the maximum load. Mentioning a direct greedy distribution first shows problem exploration, but implementing the binary search solution demonstrates stronger algorithmic judgment.
Approach 1: Binary Search over the Maximum Products
This approach uses binary search to find the minimal possible value of the maximum number of products any store can receive. For each candidate value of maximum products, validate whether the distribution is possible using this value. If distribution is possible, try to lower the maximum; otherwise, increment it.
def minimizedMaximum(n, quantities):
def canDistribute(max_products):
stores_needed = 0
for q in quantities:
stores_needed += (q + max_products - 1) // max_products
return stores_needed <= n
left, right = 1, max(quantities)
while left < right:
mid = (left + right) // 2
if canDistribute(mid):
right = mid
else:
left = mid + 1
return leftpublic int minimizedMaximum(int n, int[] quantities) {
int left = 1, right = 0;
for (int q : quantities) {
right = Math.max(right, q);
}
while (left < right) {
int mid = (left + right) / 2;
if (canDistribute(quantities, n, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
private boolean canDistribute(int[] quantities, int n, int maxProducts) {
int storesNeeded = 0;
for (int q : quantities) {
storesNeeded += (q + maxProducts - 1) / maxProducts;
}
return storesNeeded <= n;
}#include <vector>
#include <algorithm>
int minimizedMaximum(int n, std::vector<int>& quantities) {
auto canDistribute = [&](int maxProducts) {
int storesNeeded = 0;
for (int q : quantities) {
storesNeeded += (q + maxProducts - 1) / maxProducts;
}
return storesNeeded <= n;
};
int left = 1, right = *max_element(quantities.begin(), quantities.end());
while (left < right) {
int mid = (left + right) / 2;
if (canDistribute(mid)) right = mid;
else left = mid + 1;
}
return left;
}function minimizedMaximum(n, quantities) {
function canDistribute(maxProducts) {
let storesNeeded = 0;
for (let q of quantities) {
storesNeeded += Math.ceil(q / maxProducts);
}
return storesNeeded <= n;
}
let left = 1, right = Math.max(...quantities);
while (left < right) {
let mid = Math.floor((left + right) / 2);
if (canDistribute(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}#include <stdio.h>
#include <stdlib.h>
int canDistribute(int* quantities, int m, int n, int maxProducts) {
int storesNeeded = 0;
for (int i = 0; i < m; i++) {
storesNeeded += (quantities[i] + maxProducts - 1) / maxProducts;
}
return storesNeeded <= n;
}
int minimizedMaximum(int n, int* quantities, int m) {
int left = 1, right = 0;
for (int i = 0; i < m; i++) {
if (quantities[i] > right) right = quantities[i];
}
while (left < right) {
int mid = (left + right) / 2;
if (canDistribute(quantities, m, n, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}public class Solution {
public int MinimizedMaximum(int n, int[] quantities) {
int left = 1, right = 0;
foreach (int q in quantities) {
right = Math.Max(right, q);
}
while (left < right) {
int mid = (left + right) / 2;
if (CanDistribute(quantities, n, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
private bool CanDistribute(int[] quantities, int n, int maxProducts) {
int storesNeeded = 0;
foreach (int q in quantities) {
storesNeeded += (q + maxProducts - 1) / maxProducts;
}
return storesNeeded <= n;
}
}In this solution, we initialize the binary search range with left being 1 and right as the maximum quantity in the list. For each midpoint, we check if it's possible to distribute all products under this maximum threshold (using ceiling division).
Time Complexity: O(m log(max(quantities))), where m is the number of product types.
Space Complexity: O(1), as we only use a fixed amount of extra space.
Approach 2: Greedy Check with Priority Allocation
This approach tries to distribute products product-by-product to the least filled store using a priority queue. The queue handles product allocation dynamically, prioritizing lesser filled stores to balance distribution.
import heapq
def minimizedMaximum(n, quantities):
heap = [-1] * n
heapq.heapify(heap)
quantities.sort(reverse=True)
for q in quantities:
min_store = heapq.heappop(heap)
min_store -= q
heapq.heappush(heap, min_store)
return -min(heap)import java.util.PriorityQueue;
public int minimizedMaximum(int n, int[] quantities) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int i = 0; i < n; i++) {
pq.offer(0);
}
Arrays.sort(quantities);
for (int q : quantities) {
int minStore = pq.poll();
minStore += q;
pq.offer(minStore);
}
int result = 0;
for (int store: pq) {
result = Math.max(result, store);
}
return result;
}#include <queue>
#include <vector>
#include <algorithm>
int minimizedMaximum(int n, std::vector<int>& quantities) {
std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
for (int i = 0; i < n; i++) {
pq.push(0);
}
std::sort(quantities.begin(), quantities.end());
for (int q : quantities) {
int minStore = pq.top(); pq.pop();
minStore += q;
pq.push(minStore);
}
int result = 0;
while (!pq.empty()) {
result = std::max(result, pq.top());
pq.pop();
}
return result;
}The solution maintains a heap for retail stores initially set to size n with negative ones. For each quantity, the largest product is distributed to the least loaded store/s, maintaining a balanced load across stores.
Time Complexity: O(m log n + n), where m is the number of products and n the number of stores.
Space Complexity: O(n) for maintaining the heap of stores.
Approach 3: Default Approach
function minimizedMaximum(n: number, quantities: number[]): number {
let left = 1;
let right = 1e5;
while (left < right) {
const mid = (left + right) >> 1;
let cnt = 0;
for (const v of quantities) {
cnt += Math.ceil(v / mid);
}
if (cnt <= n) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}func minimizedMaximum(n int, quantities []int) int {
return 1 + sort.Search(1e5, func(x int) bool {
x++
cnt := 0
for _, v := range quantities {
cnt += (v + x - 1) / x
}
return cnt <= n
})
}Complexity comparison
| Approach | Complexity |
|---|---|
| Binary Search over the Maximum Products | Time Complexity: O(m log(max(quantities))), where m is the number of product types. |
| Greedy Check with Priority Allocation | Time Complexity: O(m log n + n), where m is the number of products and n the number of stores. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Binary Search over Maximum Products | O(m log M) | O(1) | Best general solution when the answer space is monotonic and you can check feasibility quickly |
| Greedy Priority Allocation (Heap) | O(m log n) | O(m) | Useful when modeling the problem as load balancing and repeatedly splitting the largest distribution |
Frequently asked questions
Is Minimized Maximum of Products Distributed to Any Store easy or hard?
The problem is rated Medium on LeetCode. The challenge lies in recognizing that the answer can be binary searched and that feasibility can be checked greedily using ceil division for each product quantity.
Minimized Maximum of Products Distributed to Any Store Python/Java solution
Most implementations follow the same pattern: binary search on the maximum allowed products per store and a loop that computes required stores using ceil division. The logic translates directly across Python, Java, C++, and JavaScript because it only requires arrays, loops, and integer arithmetic.
How to solve Minimized Maximum of Products Distributed to Any Store in O(n)?
A strict O(n) solution is not typical for this problem because the answer must be discovered through search over a range of possible maximum values. The common solution uses binary search combined with a linear feasibility check, resulting in O(m log M) complexity.
What is the best approach for Minimized Maximum of Products Distributed to Any Store?
The optimal approach uses binary search on the maximum number of products assigned to any store. For each candidate value, perform a greedy feasibility check by summing ceil(q / x) for every quantity. If the required number of stores is within n, the distribution works. This approach runs in O(m log M) time and O(1) space.
Is Minimized Maximum of Products Distributed to Any Store asked at Google/Amazon/Meta?
This problem reflects a common interview pattern involving binary search on the answer and load balancing constraints. Variants of this pattern appear in interviews at companies like Google, Amazon, and Meta, especially when dealing with resource allocation or minimizing the maximum load.
What data structure is used in Minimized Maximum of Products Distributed to Any Store?
The primary solution uses simple arithmetic with arrays and binary search over the answer space. An alternative implementation may use a max heap (priority queue) to repeatedly split the largest product quantity across additional stores.
What is the time complexity of Minimized Maximum of Products Distributed to Any Store?
The optimal binary search solution runs in O(m log M), where m is the number of product types and M is the maximum value in the quantities array. Each binary search step scans the array once to compute the number of stores required for the candidate maximum.