Minimum Number of Days to Make m Bouquets — BS on Answer

Sanjeev SharmaSanjeev Sharma
1 min read

Advertisement

Problem 315 · Minimum Number of Days to Make m Bouquets

Difficulty: Medium · Pattern: BS on Answer

On day d, flower i blooms if bloomDay[i] <= d. Find min d to make m bouquets of k consecutive flowers.

Solutions

# Python
def minDays(bloomDay, m, k):
    if len(bloomDay) < m*k: return -1
    def feasible(d):
        bouquets = flowers = 0
        for b in bloomDay:
            if b <= d: flowers += 1
            else: flowers = 0
            if flowers == k: bouquets += 1; flowers = 0
        return bouquets >= m

    lo, hi = min(bloomDay), max(bloomDay)
    while lo < hi:
        mid = (lo+hi)//2
        if feasible(mid): hi = mid
        else: lo = mid+1
    return lo
// Java
public int minDays(int[] bloomDay, int m, int k) {
    if ((long)m*k>bloomDay.length) return -1;
    int lo=Integer.MAX_VALUE, hi=0;
    for (int d:bloomDay) { lo=Math.min(lo,d); hi=Math.max(hi,d); }
    while (lo<hi) {
        int mid=lo+(hi-lo)/2, bq=0, fl=0;
        for (int d:bloomDay) { if(d<=mid){fl++;if(fl==k){bq++;fl=0;}}else fl=0; }
        if (bq>=m) hi=mid; else lo=mid+1;
    }
    return lo;
}

Complexity

  • Time: O(n log(max-min))
  • Space: O(1)

Advertisement

Sanjeev Sharma

Written by

Sanjeev Sharma

Full Stack Engineer · E-mopro