LeetCode #1482 Medium

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.

binary-searcharraybinary-search-on-answer

Open on LeetCode ↗

02

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.

03

Approach

1

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.

2

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.

3

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)).

04

Solution & live demo

python

▶1class Solution:
▶2    def minDays(self, bloomDay, m, k):
▶3        if m * k > len(bloomDay):
▶4            return -1
▶5        lo, hi, best = min(bloomDay), max(bloomDay), -1
▶6        while lo <= hi:
▶7            day = (lo + hi) // 2
▶8            made, run = 0, 0
▶9            for b in bloomDay:
▶10                if b <= day:
▶11                    run += 1
▶12                    if run == k:
▶13                        made += 1
▶14                        run = 0
▶15                else:
▶16                    run = 0
▶17            if made >= m:
▶18                best = day
▶19                hi = day - 1
▶20            else:
▶21                lo = day + 1
▶22        return best

05

Edge cases

m * k > number of flowers

Impossible regardless of waiting; return -1 before starting the search.

k == 1

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.

Runs longer than k

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.

All flowers bloom on the same day

The answer is that day, provided enough flowers exist. The search collapses to a single value.

06

Complexity

Time

O(n log max(bloomDay))

Space

O(1)

One linear counting pass per probe. Trying every day from 1 to max would be O(n x max) and far too slow.