630. Minimum Number of Days to Make m Bouquets
A row of n flowers grows in a garden. Flower i opens on day bloomDay[i] and stays open from then on.
You want to assemble m bouquets. One bouquet requires exactly k flowers that are adjacent in the row and already open, and every flower can go into at most one bouquet.
Given the integer array bloomDay and the integers m and k, return the smallest day number on which making all m bouquets is possible. If the garden can never supply them (there are fewer than m · k flowers), return -1.
Example 1:
Input: bloomDay = [1, 10, 3, 10, 2], m = 3, k = 1
Output: 3
Explanation: Bouquets need only one flower each (k = 1). On day 3, flowers at positions 0, 2, and 4 are open — exactly the 3 bouquets needed. On day 2 only two flowers are open, so 3 is the minimum.
Example 2:
Input: bloomDay = [7, 7, 7, 7, 13, 11, 12, 7], m = 2, k = 3
Output: 12
Explanation: On day 12 the open flowers form the runs [7,7,7,7] and [11,12,7]: the first run yields one bouquet of 3, the second yields another. On day 11 the right side only has runs of length 1, so a second bouquet is impossible.
Constraints:
- 1 ≤ n = bloomDay.length ≤ 10⁵
- 1 ≤ bloomDay[i] ≤ 10⁹
- 1 ≤ m ≤ 10⁶
- 1 ≤ k ≤ n
- Return -1 when m · k > n (note m · k can exceed 32-bit range).
Hints:
Fix a day d and ask a simpler question: can I make m bouquets using only flowers with bloomDay <= d? That check is a single left-to-right scan counting runs of adjacent open flowers.
If day d works, every later day also works; if d fails, every earlier day fails too. A yes/no answer that is monotone in d is exactly the shape binary search needs — search the smallest d between min(bloomDay) and max(bloomDay) that passes.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: bloomDay = [1, 10, 3, 10, 2], m = 3, k = 1
Expected output: 3