Minimum Number of Days to Make m Bouquets
bloomDay[i] is the day flower i blooms. A bouquet needs k adjacent bloomed flowers. Return the minimum number of days to wait to make m bouquets, or -1 if it is impossible.
Intuition
Waiting longer never destroys a bouquet — flowers only bloom, never wilt — so the number of makeable bouquets is non-decreasing in the number of days waited. That monotonicity is the licence to binary search the day. Checking a specific day is a single pass: walk the array, count consecutive bloomed flowers, and every time the run reaches k, bank a bouquet and reset the run to zero.
Binary search the answer over days, with a linear feasibility check that counts completed runs of k adjacent bloomed flowers. Monotonicity holds because flowers never un-bloom: if day d works, every later day works too. The search range is min(bloomDay) to max(bloomDay) — only actual bloom days can be answers.
Approach
Rule out the impossible case first
Making m bouquets of k flowers each consumes m * k flowers. If the garden has fewer flowers than that, no amount of waiting helps — return -1 immediately. Doing this check up front avoids relying on the binary search to discover it, and in an interview it shows you read the constraints.
Count bouquets on a given day
Fix a candidate day d. Sweep the array keeping a run length of consecutive flowers with bloomDay[i] <= d. When the run hits k, increment the bouquet count and reset the run to 0 — those k flowers are consumed and cannot be reused by an overlapping bouquet. Any flower with bloomDay[i] > d breaks the run. One O(n) pass gives the bouquet count for that day.
Binary search the day
The search range is [min(bloomDay), max(bloomDay)] — waiting less than the earliest bloom yields nothing, and waiting past the latest bloom adds nothing. Probe the midpoint: if the count reaches m, record the day and search earlier; otherwise search later. The result is the earliest day with enough bouquets. O(n log max(bloomDay)).
Solution & live demo
Common pitfalls
Skipping the impossibility check
lo, hi = min(bloomDay), max(bloomDay)
if m * k > len(bloomDay):
return -1If the garden has fewer than m * k flowers total, no day ever suffices and the search returns the initial -1 only by accident of initialisation. Testing up front makes the impossible case explicit and correct.
Not resetting the run counter after completing a bouquet
if run == k:
made += 1if run == k:
made += 1
run = 0Bouquets consume their flowers. Leaving run at k means every subsequent bloomed flower completes another bouquet from the same stems, wildly overcounting and accepting far too early a day.
Leaving the run intact across an unbloomed flower
if b <= day:
run += 1if b <= day:
run += 1
...
else:
run = 0The k flowers must be adjacent. An unbloomed flower breaks the chain, so the counter has to restart — otherwise runs are stitched together across gaps that don't exist.
Edge cases
Impossible regardless of waiting; return -1 before starting the search.
Adjacency stops mattering — any m bloomed flowers suffice. The counting pass handles this without a special branch since every run of length 1 immediately banks a bouquet.
A run of 2k yields two bouquets. Resetting the run counter to 0 after each bouquet (rather than decrementing by k) gives the same result and is simpler.
The answer is that day, provided enough flowers exist. The search collapses to a single value.