2064. Minimized Maximum of Products Distributed to Any Store

Time: O(n log max)

Space: O(1)

Approach

Binary search on max products per store; validate by summing ceil(qty/mid) for each product type.

Key Techniques

Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.

Binary Search

Binary search reduces search space by half each step, giving O(log n) time. Beyond sorted arrays, apply it on the answer space ("binary search on result") when you can define a monotonic predicate — e.g., "can we achieve X with k resources?"

2064.cs

// Approach: Binary search on max products per store; validate by summing ceil(qty/mid) for each product type.
// Time: O(n log max) Space: O(1)

public class Solution
{
    public int MinimizedMaximum(int n, int[] quantities)
    {
        int l = 1;
        int r = quantities.Max();

        while (l < r)
        {
            int m = (l + r) / 2;
            if (NumStores(quantities, m) <= n)
                r = m;
            else
                l = m + 1;
        }

        return l;
    }

    private int NumStores(int[] quantities, int m)
    {
        // ceil(q / m)
        return quantities.Sum(q => (q - 1) / m + 1);
    }
}

Was this solution helpful?