Minimum Number of Days to Make m Bouquets

medium array binary search

Problem

Given bloomDay[i] (day flower i blooms), m bouquets each needing k adjacent flowers — return minimum days to make all m, or -1 if impossible.

InputbloomDay=[1,10,3,10,2], m=3, k=1

Output3

By day 3, flowers at indices 0,2,4 are bloomed — 3 single-flower bouquets.

bloomDay

def min_days(bloomDay, m, k):
    if m * k > len(bloomDay): return -1
    def can(d):
        bouquets = run = 0
        for x in bloomDay:
            if x <= d:
                run += 1
                if run == k: bouquets += 1; run = 0
            else:
                run = 0
        return bouquets >= m
    lo, hi = min(bloomDay), max(bloomDay)
    while lo < hi:
        mid = (lo + hi) // 2
        if can(mid): hi = mid
        else: lo = mid + 1
    return lo

function minDays(bd, m, k) {
  if (m * k > bd.length) return -1;
  function can(d) { let b = 0, r = 0; for (const x of bd) { if (x <= d) { r++; if (r === k) { b++; r = 0; } } else r = 0; } return b >= m; }
  let lo = Math.min(...bd), hi = Math.max(...bd);
  while (lo < hi) { const mid = (lo + hi) >>> 1; if (can(mid)) hi = mid; else lo = mid + 1; }
  return lo;
}

class Solution {
    public int minDays(int[] bd, int m, int k) {
        if ((long) m * k > bd.length) return -1;
        int lo = Integer.MAX_VALUE, hi = 0;
        for (int x : bd) { lo = Math.min(lo, x); hi = Math.max(hi, x); }
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (can(bd, m, k, mid)) hi = mid; else lo = mid + 1;
        }
        return lo;
    }
    boolean can(int[] bd, int m, int k, int d) {
        int b = 0, r = 0;
        for (int x : bd) { if (x <= d) { r++; if (r == k) { b++; r = 0; } } else r = 0; }
        return b >= m;
    }
}

int minDays(vector& bd, int m, int k) {
    if ((long long) m * k > (int)bd.size()) return -1;
    int lo = *min_element(bd.begin(), bd.end()), hi = *max_element(bd.begin(), bd.end());
    auto can = [&](int d) {
        int b = 0, r = 0;
        for (int x : bd) { if (x <= d) { r++; if (r == k) { b++; r = 0; } } else r = 0; }
        return b >= m;
    };
    while (lo < hi) { int mid = (lo + hi) / 2; if (can(mid)) hi = mid; else lo = mid + 1; }
    return lo;
}

Explanation

Waiting more days can only help: any flower bloomed by day d is still bloomed by day d+1. So "can we make m bouquets by day d?" is monotone, and we binary-search the day d.

First a quick check: if m * k exceeds the number of flowers, it is impossible, so we return -1. Otherwise the feasibility test can(d) scans the flowers left to right, counting a run of consecutive bloomed flowers (those with bloomDay <= d). Each time the run reaches k we complete a bouquet and reset the run; a flower not yet bloomed breaks the run.

If can(mid) makes at least m bouquets, that day works so we shrink (hi = mid); otherwise we wait longer (lo = mid + 1). The range runs from the earliest to the latest bloom day.

Example: bloomDay = [1,10,3,10,2], m = 3, k = 1. By day 3 the flowers with values 1, 3, 2 (indices 0, 2, 4) are open, giving 3 single-flower bouquets, and no earlier day reaches 3. So the answer is 3.

Because bouquets need adjacent bloomed flowers, the run-reset logic correctly handles gaps where a flower has not bloomed yet.

Time: O(n log(max−min)) Space: O(1)