DSA problem
Minimum Number of Days to Make m Bouquets
You are given an integer array bloomDay, an integer m, and an integer k. You want to make m bouquets. To make a bouquet, you need to use k adjacent flowers from the garden. The garden has n flowers; the i-th flower will bloom in the bloomDay[i]-th day and then can be used in any bouquet. Return the minimum number of days you need to wait to be able to make m bouquets from the garden. If it is impossible to make m bouquets return -1.
Like Koko and Ship Capacity, this is binary search the answer. Define canMake(day) = "on day day, can we form at least m bouquets?" The predicate is monotonic: if day suffices, every later day also suffices. So the valid days form a suffix, and binary searching the boundary gives the answer.
The predicate runs a single linear scan of bloomDay. Walk left to right, counting the current run of consecutive bloomed (bloomDay[i] <= day) flowers; whenever the run reaches k, count one bouquet and reset the run. Return whether the bouquet count reached m.
The search range for day is [min(bloomDay), max(bloomDay)]. The lower bound is the earliest any flower blooms; the upper bound is the latest. If m * k > n, return -1 immediately because not enough flowers can ever bloom. Use the lower-bound shape: lo = min(bloomDay), hi = max(bloomDay), narrow hi to mid when canMake(mid). Time O(n log(max - min)), space O(1).
Examples
bloomDay = [1,10,3,10,2], m = 3, k = 13bloomDay = [1,10,3,10,2], m = 3, k = 2-1bloomDay = [7,7,7,7,12,7,7], m = 2, k = 312Constraints
- bloomDay.length == n
- 1 <= n <= 10^5
- 1 <= bloomDay[i] <= 10^9
- 1 <= m <= 10^6
- 1 <= k <= n
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.