Minimum Number of Days to Make m Bouquets
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.
- bloomDay.length == n
- 1 <= n <= 10⁵
- 1 <= bloomDay[i] <= 10⁹
- 1 <= m <= 10⁶
- 1 <= k <= n
Intuition
Minimum number of days to make m bouquets finds the earliest day when m bouquets can be made, each needing k adjacent flowers that have already bloomed.
The answer is a day number, and days have a natural order — which is the opening for binary search:
- Waiting longer never makes fewer bouquets possible, so feasibility is monotonic in the day, and binary search applies to the day itself.
That is binary search on the answer, not on the array, so the input order must be preserved.
For a candidate day, the check is a single linear scan. Walk the flowers counting consecutive blooms — those whose bloom day is at most the candidate. Each time the run reaches k, count a bouquet and reset the run to zero. Any flower not yet bloomed also resets it.
Resetting to zero after forming a bouquet is essential. Leaving the counter running lets the same flowers be reused across overlapping bouquets, which the adjacency requirement forbids, and the check then reports feasible far too early.
The search range runs from the minimum bloom day to the maximum. Below the minimum nothing has bloomed; above the maximum nothing more will change.
One check comes before the search: if m × k exceeds the flower count, there are not enough flowers to ever succeed, so return −1. The multiplication can overflow on large inputs, so compare as m > n / k or use a wider type.
Each feasibility check is O(n) and the range halves each step, giving O(n log(maxDay − minDay)).
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
Before reading on: price up what the direct approach costs here, then ask what property lets you throw away half the range after one comparison. Aim for O(n log max(bloomDay)) time and O(1) space.
Spot the monotonic predicate
Waiting longer never reduces the bouquets available, so feasibility flips from false to true exactly once — the condition binary search needs.
Rule out impossible inputs first
If m bouquets of k flowers exceed the total, return -1. Compare as m > n / k — the multiplication overflows on large inputs.
Set the search range
Search days from the minimum bloom day to the maximum. Below the first nothing has bloomed; above the last nothing further changes.
Count consecutive blooms
For a candidate day, scan once counting runs of flowers bloomed by then. A flower not yet bloomed breaks the run and resets the counter.
Reset after each bouquet
Set the run back to zero once k flowers are gathered. Letting it continue reuses the same flowers across bouquets and reports success far too early.
Narrow toward the earliest day
When a day is feasible, record it and search earlier; otherwise search later. The loop converges on the minimum workable day.
Cost of the search
Each check is O(n) and the range halves each step, giving O(n log(maxDay − minDay)) time and O(1) space.
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.