⚡Flashcard Drill➔
NeetCode #281LC-2064MediumBinary Search
← Back to All Problems

#281 · #2064 · Minimized Maximum of Products Distributed to Any Store(分配给商店的最多商品的最小值)

📌 Problem Statement & Constraints

You are given n stores and an array quantities where quantities[i] is the number of products of type i. You must distribute all products to the stores, and each store receives products of only one type. Return the minimum possible maximum number of products given to any store. Constraints: 1 <= n <= 10^5, 1 <= m <= 10^5, 1 <= quantities[i] <= 10^5.

💡 Core Algorithmic Approaches

  1. Binary search on the answer x: "can every store receive at most x products" is monotone in x.
  2. For a given x, the number of stores needed for type i is ceil(quantities[i] / x), so the total is sum(ceil(q / x)).
  3. The answer is feasible when the total is at most n. Use hi = mid to find the smallest feasible x.
  4. The lower bound is 1 and the upper bound is max(quantities), since one store can always take a whole type.

💻 Benchmark Python3 Implementation

class Solution:
    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:
        lo, hi = 1, max(quantities)
        while lo < hi:
            mid = (lo + hi) // 2
            # stores needed if each store takes at most mid products
            stores = sum((q + mid - 1) // mid for q in quantities)
            if stores <= n:
                hi = mid               # feasible -> try a smaller cap
            else:
                lo = mid + 1
        return lo

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m log(max(quantities))): each feasibility check is O(m).
💾 Space Complexity
O(1): a few scalars.

⚠️ Interview Pitfalls & Follow-ups

  • Using q // mid instead of the ceiling: integer division truncates, so the store count would be underestimated.
  • Using hi = mid - 1 when feasible: could skip the optimum.
  • Assuming products can be split across stores: each store receives only one type, which is why the ceiling division is per type.
  • Setting the lower bound to 0: a cap of 0 is infeasible whenever any quantity is positive.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Binary Search Problems