Minimum Number of Days to Make m Bouquets

Binary search the day, scan adjacent runs to test it

time O(n log(max(bloomDay)))space O(1)

The array is not sorted and sorting it would destroy the adjacency the bouquets depend on, so there is nothing here to binary search directly. What IS ordered is the calendar: a flower open on day 9 is still open on day 10, so the number of bouquets available never falls as the day rises. Feasibility flips from no to yes exactly once along that line, and binary search hunts that flip. Each guessed day is tested by one left-to-right walk that counts the current run of open flowers, cutting a bouquet every time the run reaches k and resetting the run at any flower still in bud.

Details

Animated on: bloomDay = [7,7,7,7,13,11,12,7], m = 2, k = 3 — each bouquet needs 3 ADJACENT flowers that have already bloomed; find the earliest day 2 bouquets can be made.

Problem:Minimum Number of Days to Make m BouquetsMedium

Pattern:Binary Search on Answer

Binary search the day, scan adjacent runs to test it

step 1 / 9

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Each cell is the day that flower opens. We need 2 bouquets of 3 ADJACENT flowers each, and picking one never blocks another, so the only question is which day to harvest. Nothing opens before day 7 and everything is open by day 13, so the answer lives in [7, 13].

Pseudocode

1FUNCTION minDays(bloom, m, k):
2  IF m * k > LENGTH(bloom):
3    RETURN -1
4  low <- MIN(bloom)
5  high <- MAX(bloom)
6  WHILE low < high:
7    mid <- (low + high) / 2
8    IF BOUQUETS(bloom, mid, k) >= m:
9      high <- mid
10    ELSE:
11      low <- mid + 1
12  RETURN low

← / → step · space play · Home restart

Every step in words

Show all 9 steps

Each cell is the day that flower opens. We need 2 bouquets of 3 ADJACENT flowers each, and picking one never blocks another, so the only question is which day to harvest. Nothing opens before day 7 and everything is open by day 13, so the answer lives in [7, 13].
2 bouquets consume 6 flowers and the garden has 8, so an answer exists. Waiting longer only ever opens MORE flowers, so once a day works every later day works too — that one-way flip is what binary search hunts.
Range is [7, 13] — 7 days still possible. Test the middle one, day 10: whichever way it answers, half of those days are gone.
By day 10, 5 of the 8 flowers are open but the open ones only yield 1 bouquet ([0,1,2]) — the greyed buds keep breaking the runs apart. 1 < 2, and any earlier day has even fewer flowers open, so discard the whole lower half: low <- 11.
Range is [11, 13] — 3 days still possible. Test the middle one, day 12: whichever way it answers, half of those days are gone.
By day 12, 7 of the 8 flowers are open and scanning left to right cuts 2 bouquets [0,1,2] + [5,6,7] — 2 >= 2, so day 12 is enough. An earlier day might still be, so keep 12 as a candidate and drop everything after it: high <- 12.
Range is [11, 12] — 2 days still possible. Test the middle one, day 11: whichever way it answers, half of those days are gone.
By day 11, 6 of the 8 flowers are open but the open ones only yield 1 bouquet ([0,1,2]) — the greyed buds keep breaking the runs apart. 1 < 2, and any earlier day has even fewer flowers open, so discard the whole lower half: low <- 12.
low and high have met at 12. Every earlier day was proven short of 2 bouquets, and day 12 yields 2 — [0,1,2] + [5,6,7] — so 12 is the earliest day the garden can fill the order.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Minimum Number of Days to Make m Bouquets in the editor All Binary Search problems Back to roadmap