LeetCode 2064 - Minimized Maximum of Products Distributed to Any Store

The problem gives us n retail stores and an array quantities, where each element represents how many products exist for a particular product type. The important restriction is that a single store may contain products from only one product type.

leetcodemediumarraybinary-searchgreedy

LeetCode Problem 2064

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Greedy

Solution

Problem Understanding

The problem gives us n retail stores and an array quantities, where each element represents how many products exist for a particular product type.

The important restriction is that a single store may contain products from only one product type. However, a product type may be split across multiple stores. Our goal is to distribute all products while minimizing the maximum number of products assigned to any single store.

In other words, suppose the final answer is x. That means no store is allowed to hold more than x products. We need to determine the smallest possible value of x such that every product can still be distributed legally.

For example, if a product type has 11 items and we decide that no store can hold more than 3 items, then that product type would require:

$$\lceil 11 / 3 \rceil = 4$$

stores, because each store can hold at most 3 of that type.

The input consists of:

  • n, the total number of available stores
  • quantities, where quantities[i] is the count of the i-th product type

The output is a single integer, the minimum possible maximum load per store.

The constraints are important:

  • 1 <= m <= n <= 10^5
  • 1 <= quantities[i] <= 10^5

The number of product types and stores can both be as large as 100000, so any algorithm worse than roughly O(m log k) will likely be too slow, where k is the maximum quantity value.

Several edge cases are important:

  • Only one store exists, so all products must go into that store.
  • A product type may be much larger than the others.
  • The optimal answer may equal the maximum quantity if there are very few stores.
  • The answer may be very small if there are many stores available.
  • Integer division errors are easy to make when computing ceiling values.

Approaches

Brute Force Approach

A straightforward idea is to try every possible value of x from 1 up to max(quantities).

For each candidate x, we calculate how many stores are required. If a product type contains q items, and each store may hold at most x, then the number of stores needed is:

$$\lceil q / x \rceil$$

We sum this over all product types. If the total required stores is less than or equal to n, then x is feasible.

This approach is correct because it explicitly checks every possible answer and returns the smallest feasible one.

However, it is too slow. If the largest quantity is 100000, then we may perform 100000 checks, and each check scans the entire array.

This leads to:

$$O(m \times \max(quantities))$$

which is too expensive for the constraints.

Optimal Approach, Binary Search on the Answer

The key observation is that feasibility is monotonic.

If a value x works, then every larger value also works.

For example:

  • If stores can hold at most 5 products and distribution is possible,
  • then allowing stores to hold 6, 7, or more products will also be possible.

This monotonic property makes the problem ideal for binary search.

We binary search the answer range:

  • Minimum possible answer: 1
  • Maximum possible answer: max(quantities)

For each midpoint mid, we determine whether distribution is feasible.

To check feasibility:

  • For every quantity q,
  • compute required stores as:

$$\lceil q / mid \rceil$$

  • Sum these values.
  • If total stores needed is <= n, then mid is feasible.

Using binary search reduces the complexity dramatically.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(m × max(quantities)) O(1) Tries every possible maximum value
Optimal O(m log(max(quantities))) O(1) Uses binary search on feasible answers

Algorithm Walkthrough

  1. Initialize the binary search boundaries.

The smallest possible answer is 1 because a store must hold at least one product if products exist.

The largest possible answer is max(quantities) because one store could theoretically hold an entire product type. 2. Start binary search while left < right.

At each iteration, compute:

mid = (left + right) // 2

This mid represents a candidate maximum number of products per store. 3. Check whether mid is feasible.

For each quantity q, calculate how many stores are needed if no store can exceed mid products.

The formula is:

$$\lceil q / mid \rceil$$

In integer arithmetic, this becomes:

(q + mid - 1) // mid
  1. Sum the required stores across all product types.

If the total required stores is less than or equal to n, then the candidate mid is feasible.

That means we may be able to do even better with a smaller maximum value.

Move the right boundary:

right = mid
  1. Otherwise, mid is too small.

We need more stores than available, so increase the allowed maximum:

left = mid + 1
  1. Continue until the search space collapses.

When left == right, we have found the minimum feasible value.

Why it works

The algorithm relies on the monotonic nature of feasibility.

If a maximum store load x is sufficient, then any larger value will also be sufficient because larger capacities can only reduce the number of stores needed.

Binary search correctly identifies the smallest feasible value in this monotonic search space.

Python Solution

from typing import List

class Solution:
    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:
        left = 1
        right = max(quantities)

        while left < right:
            mid = (left + right) // 2

            required_stores = 0

            for quantity in quantities:
                required_stores += (quantity + mid - 1) // mid

            if required_stores <= n:
                right = mid
            else:
                left = mid + 1

        return left

The implementation starts by defining the binary search range. The lower bound is 1, and the upper bound is the largest product quantity.

Inside the binary search loop, the code evaluates whether mid is feasible. The variable required_stores accumulates how many stores are needed if no store may exceed mid products.

The ceiling division formula:

(quantity + mid - 1) // mid

ensures correct rounding upward without using floating point arithmetic.

If the total required stores fits within n, the algorithm narrows the search to smaller values by updating right.

Otherwise, the candidate is too small, so the algorithm increases the lower bound.

Eventually, both pointers converge to the smallest feasible answer.

Go Solution

func minimizedMaximum(n int, quantities []int) int {
	left := 1
	right := 0

	for _, quantity := range quantities {
		if quantity > right {
			right = quantity
		}
	}

	for left < right {
		mid := left + (right-left)/2

		requiredStores := 0

		for _, quantity := range quantities {
			requiredStores += (quantity + mid - 1) / mid
		}

		if requiredStores <= n {
			right = mid
		} else {
			left = mid + 1
		}
	}

	return left
}

The Go implementation follows the same logic as the Python solution.

One small difference is the calculation of the midpoint:

mid := left + (right-left)/2

This form avoids potential integer overflow, although overflow is not realistically possible under the given constraints.

Go uses slices for quantities, and integer division already truncates toward zero, making the ceiling division formula work naturally.

Worked Examples

Example 1

Input:

n = 6
quantities = [11, 6]

Initial search range:

left = 1
right = 11
Iteration left right mid Stores Needed for 11 Stores Needed for 6 Total Stores Feasible
1 1 11 6 2 1 3 Yes
2 1 6 3 4 2 6 Yes
3 1 3 2 6 3 9 No

After iteration 3:

left = 3
right = 3

Answer:

3

Example 2

Input:

n = 7
quantities = [15, 10, 10]

Initial range:

left = 1
right = 15
Iteration left right mid Stores for 15 Stores for 10 Stores for 10 Total Feasible
1 1 15 8 2 2 2 6 Yes
2 1 8 4 4 3 3 10 No
3 5 8 6 3 2 2 7 Yes
4 5 6 5 3 2 2 7 Yes

Final answer:

5

Example 3

Input:

n = 1
quantities = [100000]

Only one store exists.

Therefore, the entire quantity must go into that store.

Answer:

100000

Complexity Analysis

Measure Complexity Explanation
Time O(m log(max(quantities))) Binary search performs log(max quantity) iterations, each scanning all product types
Space O(1) Only a few variables are used

The binary search range spans from 1 to max(quantities). Since the maximum quantity is at most 100000, the binary search performs at most about 17 iterations.

During each iteration, we scan the quantities array once to compute required stores.

This gives a total complexity of:

$$O(m \log(\max(quantities)))$$

which easily fits within the constraints.

Test Cases

from typing import List

class Solution:
    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:
        left = 1
        right = max(quantities)

        while left < right:
            mid = (left + right) // 2

            required_stores = 0

            for quantity in quantities:
                required_stores += (quantity + mid - 1) // mid

            if required_stores <= n:
                right = mid
            else:
                left = mid + 1

        return left

solution = Solution()

assert solution.minimizedMaximum(6, [11, 6]) == 3  # example 1
assert solution.minimizedMaximum(7, [15, 10, 10]) == 5  # example 2
assert solution.minimizedMaximum(1, [100000]) == 100000  # single store

assert solution.minimizedMaximum(3, [1, 1, 1]) == 1  # exact one item per store
assert solution.minimizedMaximum(4, [8]) == 2  # one product split across many stores
assert solution.minimizedMaximum(5, [10, 10]) == 5  # balanced split
assert solution.minimizedMaximum(10, [1, 2, 3]) == 1  # many extra stores
assert solution.minimizedMaximum(2, [99999, 1]) == 99999  # dominant large quantity
assert solution.minimizedMaximum(9, [9, 9, 9]) == 3  # equal distribution
assert solution.minimizedMaximum(100000, [1] * 100000) == 1  # maximum constraints
Test Why
n=6, quantities=[11,6] Validates the first provided example
n=7, quantities=[15,10,10] Validates the second provided example
n=1, quantities=[100000] Tests single-store boundary
n=3, quantities=[1,1,1] Smallest possible answer
n=4, quantities=[8] One product type spread across multiple stores
n=5, quantities=[10,10] Balanced distribution
n=10, quantities=[1,2,3] Many unused stores available
n=2, quantities=[99999,1] Large imbalance between product types
n=9, quantities=[9,9,9] Symmetric distribution
n=100000, quantities=[1]*100000 Stress test for maximum input size

Edge Cases

One important edge case occurs when there is only a single store. In that situation, all products must be assigned to the same store, meaning the answer must equal the largest quantity. A buggy implementation might incorrectly attempt to split products further even though no additional stores exist. The binary search correctly handles this because every smaller candidate becomes infeasible.

Another important case is when there are many extra stores available. For example, if n is much larger than the total number of products, the optimal answer may become 1. Some implementations accidentally assume every store must contain products, which is false. The problem explicitly allows empty stores, and this solution naturally supports that behavior.

A third tricky case involves ceiling division. Suppose we have 11 products and a limit of 3 per store. Using normal integer division:

11 // 3 = 3

would incorrectly suggest only three stores are needed. In reality, four stores are required because the remainder still needs storage. The implementation avoids this bug using:

(quantity + mid - 1) // mid

which correctly computes ceiling division using integer arithmetic.

Another subtle edge case appears when one product type dominates all others. For example:

quantities = [99999, 1]

with very few stores. The algorithm still works because feasibility depends only on the total number of required stores, regardless of how uneven the quantities are.