Skip to main content
Talentd

Minimized Maximum of Products Distributed to Any Store - Solution & Explanation

MediumArrayBinary SearchGreedy12 min readAsked at: Amazon, Microsoft, Siemens +2
Practice this problem

Problem Statement

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). Let x represent the maximum number of products given to any store. You want x to 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.length
  • 1 <= m <= n <= 105
  • 1 <= 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.

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).

Code

PythonJavaC++CC#JavaScript

Python

Java

C++

C

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

PythonJavaC++

Python

Java

C++

Complexity

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.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Binary Search over the Maximum Products

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.

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.
Space Complexity: O(n) for maintaining the heap of stores.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Binary Search over Maximum ProductsO(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

Video Solution

Minimized Maximum of Products Distributed to Any Store - Leetcode 2064 - Python • NeetCodeIO • 10,786 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Minimized Maximum of Products Distributed to Any Store with our built-in code editor and test cases.

Practice on FleetCode
Previous

Capacity To Ship Packages Within D Days

Next

Find the Smallest Divisor Given a Threshold