Minimum Number of Days to Make m Bouquets
Medium · Binary Search · Array · Binary Search
Problem
A garden has n flowers in a row. Flower i blooms on day bloomDay[i] and stays in bloom from then on.
A bouquet takes k adjacent bloomed flowers, and each flower can go into at most one bouquet. Return the fewest days you must wait to make m bouquets, or -1 if it can never be done.
Examples
Input: bloomDay = [2,9,3,4,1,8], m = 2, k = 2 Output: 8
On day 8, flowers 2, 3, 4 and 5 have bloomed: two adjacent pairs. On day 4 only flowers 2 and 3 form a pair next to each other.
Input: bloomDay = [5,5,5], m = 2, k = 2 Output: -1
Two bouquets of two need four flowers, and the garden has three.
Input: bloomDay = [6,1,3], m = 3, k = 1 Output: 6
Every flower is its own bouquet, so you wait for the last one, on day 6.
Constraints
- n == len(bloomDay)
- 1 <= n <= 10^5
- 1 <= bloomDay[i] <= 10^9
- 1 <= m <= 10^6
- 1 <= k <= n
Approaches
- Try every bloom day in order — time O(n²), space O(n)
Follow-up
What if many people ask the same garden for different (m, k) pairs? Each question is still one binary search, but for a fixed k you could precompute, for every number of bouquets, the earliest day it becomes possible, and answer each m by a lookup.
Related problems
Start free on Cariara · Coding problems · System design studio
