medium +25 pts

Minimum Days to Make Bouquets

Find the earliest day to make m bouquets from blooming flowers.

You own a garden with `n` flowers. The `i`-th flower blooms on day `bloomDay[i]`. You want to make exactly `m` bouquets, and each bouquet requires `k` **adjacent** flowers (i.e., `k` consecutive blooming flowers in the array). Once a flower blooms, it stays bloomed forever. Write a function `min_days(bloomDay: List[int], m: int, k: int) -> int` that returns the **minimum** day on which you can make `m` bouquets. If it is impossible, return `-1`. Adjacent means flowers that are next to each other in the original array. You cannot reuse a flower in more than one bouquet. You may make bouquets from any contiguous block of `k` blooming flowers, and blocks do not overlap. Your solution must run in O(n log(max(bloomDay))) time.

Constraints

`1 <= bloomDay.length <= 10^5` `1 <= m <= 10^5` `1 <= k <= 10^5` `1 <= bloomDay[i] <= 10^9` The product `m * k` may exceed the total number of flowers, in which case return -1.

Example

>>> min_days([1,10,3,10,2], 3, 1)
3
>>> min_days([1,10,3,10,2], 3, 2)
-1
>>> min_days([7,7,7,7,12,7,7], 2, 3)
12
25 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about binary searching the answer: on a given day `D`, how many bouquets can you make?
To check a day, scan the array and count consecutive bloomed flowers; whenever you hit `k` in a row, increment bouquet count and reset the run.
If `m * k` is greater than the number of flowers, return -1 immediately.
The answer is monotonic: if you can make the bouquets by day D, you can by any later day.
Python 3
All tests passed!
Test Results
Press Ctrl+Enter or click Run Tests to execute your code.