2064. Minimized Maximum of Products Distributed to Any Store

This page provides solutions for the leetcode problem 2064. Minimized Maximum of Products Distributed to Any Store.

Problem Explanation

The problem is asking us to distribute product, given in a product array $\text{quantities}$, into $\text{n}$ stores such that each store is given at most a single product type but in any quantity. This distribution should try to minimize the maximum number of products a single store has.

Solution

This problem can be solved using the Binary Search technique. More such questions can be found here.

Java

class Solution {
  public int minimizedMaximum(int n, int[] quantities) {
    int lo = 1;
    int hi = Integer.MIN_VALUE;
    for(int i = 0; i < quantities.length; i++) {
      hi = Math.max(hi, quantities[i]);
    }

    while(lo < hi) {
      int mid = (lo + hi) / 2;
      int partitions = getPartitions(quantities, mid);
      if(partitions > n) lo = mid + 1;
      else hi = mid;
    }
    return lo;
  }

  private int getPartitions(int[] quantities, int required) {
    int partitions = 0;
    for(int i = 0; i < quantities.length; i++) {
      partitions += quantities[i] / required;
      if(quantities[i] % required != 0) partitions++;           
    }
    return partitions;
  }
}

Complexity

Let's say there are $\text{N}$ elements in an array, and total sum of all elements in an array is $\text{S}$.

Time Complexity

The time complexity is $\text{O}(\log \text{S})$ for searching the optimal solution using binary search, and $\text{O}(\text{N})$ for checking if the array can be split into $\text{K}$ subarrays.

Total time complexity will be,

$$\text{O}(\text{N} \log \text{S})$$

Space Complexity

The solution uses constant space for storing binary search variables.

$$\text{O}(1)$$