343. Bouquet Day
A florist plants a row of flowers, where bloomDay[i] is the day on which the i-th flower blooms and stays in bloom. She wants to make m bouquets, each made from exactly k flowers that are next to each other in the row, and every flower can only be used in one bouquet.
Return the smallest day number after which she can make all m bouquets, or -1 if the row does not have enough flowers to ever do it. Waiting a day at a time and re-counting is too slow because the bloom days can be as large as a billion.
Example 1
- Input:
- bloomDay = [3,9,4,4,5,8,2], m = 2, k = 3
- Output:
- 9
- Explanation:
On day 8 the flower at index 1 is still closed, so only one run of three open flowers fits a bouquet. On day 9 all seven flowers are open and two bouquets can be made, so the answer is 9.
Example 2
- Input:
- bloomDay = [6,6], m = 1, k = 3
- Output:
- -1
- Explanation:
Three flowers are needed in one bouquet but there are only two, so the answer is -1.
Constraints
1 ≤ bloomDay.length ≤ 105
1 ≤ bloomDay[i] ≤ 109
1 ≤ m, k ≤ 106
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n log D), where D is the largest bloom day
- Space
- O(1)