Earliest Day for Bouquets
MediumBinary Search
Problem
A florist has a row of plants; bloom[i] is the day plant i flowers (and stays in bloom). A bouquet needs k adjacent plants in bloom, and each plant can be used in at most one bouquet.
Return the earliest day on which the florist can make m bouquets, or -1 if it is impossible.
Example 1
- Input:
- bloom = [3, 8, 2, 7, 4, 1], m = 2, k = 2
- Output:
- 7
On day 7 every plant except index 1 is in bloom: indices 2-5 give two bouquets. On day 6 index 3 is still closed, leaving only indices 4-5.
Example 2
- Input:
- bloom = [5, 5, 5], m = 2, k = 2
- Output:
- -1
Two bouquets of two need four plants; there are three.
Example 3
- Input:
- bloom = [9, 1, 9], m = 1, k = 1
- Output:
- 1
Constraints
- 1 ≤ bloom.length ≤ 10^5
- 1 ≤ bloom[i] ≤ 10^9
- 1 ≤ m ≤ 10^6
- 1 ≤ k ≤ bloom.length
Hint
Show the first hint
If the bouquets can be made on day d, can they be made on day d + 1?
Walkthrough
How to approach it
01Clarify before coding
- Must the k plants be adjacent? Yes, a contiguous run.
- Do flowers stay open once bloomed? Yes, which is what makes the answer monotonic.
- When is it impossible? Exactly when m · k exceeds the number of plants; then return -1.
02Brute force
Try each distinct bloom day in increasing order and count bouquets for it.
Cost: O(n²) time in the worst case (n distinct days, an O(n) count each): 10^10 for n = 10^5.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.