Minimum Number of Days to Make m Bouquets
Understanding the Problem
We have a garden of n flowers, and each flower blooms on a specific day. We need to make m bouquets, and each bouquet requires exactly k adjacent (consecutive) flowers that have already bloomed. A flower can only be used in one bouquet.
This problem has a monotonic property. If we can make m bouquets by day d, we can also make them by day d + 1, because more flowers will have bloomed by then and no bloomed flower ever wilts. Conversely, if we cannot make m bouquets by day d, we cannot make them by any earlier day either. This "if feasible at day d, then feasible at day d+1" property means binary search on the answer applies.
The second piece is the feasibility check. Given a specific day d, we walk through the array left to right, counting consecutive bloomed flowers. Every time the consecutive count reaches k, that is one bouquet, and we reset the counter. This greedy scan tells us how many bouquets we can make on day d.
Key Constraints:
1 <= n <= 10^5--> The feasibility check (scanning the array) must be O(n) or better per call.1 <= bloomDay[i] <= 10^9--> The search space for the answer is up to 10^9, so we cannot try every day linearly. Binary search over days gives O(log(10^9)) = ~30 iterations.1 <= m <= 10^6--> We must check early whetherm * k > n. If so, the answer is immediately -1.
Approach 1: Brute Force (Try Every Bloom Day)
Intuition
Collect all unique bloom days, sort them, and try each one as a candidate answer. For each candidate day, scan the array to count how many bouquets we can make. The first day where we can make at least m bouquets is the answer.
We only check unique bloom days because the number of bloomed flowers changes only on days when a new flower blooms. Checking day 5 and day 6 gives the same result if no flower blooms on day 6, so the distinct values in bloomDay cover every meaningful candidate.
The feasibility check walks left to right, keeping a running count of consecutive bloomed flowers. Every time the count reaches k, increment the bouquet count and reset.
Algorithm
- If
m * k > n, return -1 immediately (not enough flowers). - Collect all unique bloom days and sort them in ascending order.
- For each unique day
d(smallest to largest): - Scan the
bloomDayarray left to right. - Maintain a counter of consecutive flowers where
bloomDay[i] <= d. - Every time this counter reaches
k, increment the bouquet count and reset the counter to 0. - If the bouquet count reaches
m, returnd. - If no day works, return -1.
Visualization and Code
Loading animation...
- Time Complexity: O(n * u), where n is the length of
bloomDayand u is the number of unique bloom days. In the worst case every bloom day is unique, so u = n, making this O(n^2). - Space Complexity: O(u) for storing the unique bloom days.
When most bloom days are distinct, this checks close to n candidates and degrades to O(n^2). Because the feasibility function is monotonic (once true, it stays true for all larger days), binary search can find the boundary day without checking every candidate.
Approach 2: Binary Search on Answer
Intuition
If we can make m bouquets on day d, we can also make them on day d + 1, d + 2, and every day after that. More flowers bloom as days pass, never fewer. So the feasibility function over days looks like false, false, ..., false, true, true, ..., true, and we want the first true.
That structure is what binary search exploits. Instead of searching the array for an element, we search the space of possible answers (days from min(bloomDay) through max(bloomDay)) for the smallest day that satisfies the condition.
The search space is bounded: the answer must be at least min(bloomDay) (can't make any bouquet before the first flower blooms) and at most max(bloomDay) (by then all flowers have bloomed). We binary search within this range, and at each midpoint we run our greedy feasibility check.
The feasibility scan forms a bouquet the moment it sees k consecutive bloomed flowers, then resets. This maximizes the bouquet count for a fixed day because bouquets cannot overlap: a flower used in one bouquet cannot be reused. Within any maximal run of r consecutive bloomed flowers, the best we can do is floor(r / k) bouquets, and cutting greedily from the left achieves exactly that. Holding back a complete group of k flowers in the hope of a better grouping later can only lower the total, so the greedy count equals the true maximum for that day.
Algorithm
- If
m * k > n, return -1 immediately (not enough flowers even if all bloom). - Set
low = min(bloomDay)andhigh = max(bloomDay). - While
low < high: - Compute
mid = low + (high - low) / 2. - Run the feasibility check: scan the array, count consecutive flowers where
bloomDay[i] <= mid, and count bouquets. - If we can make at least
mbouquets, sethigh = mid(this day works, but maybe an earlier day also works). - Otherwise, set
low = mid + 1(need more days). - Return
low.
Visualization and Code
Loading animation...
- Time Complexity: O(n * log(max - min)), where n is the length of
bloomDayand max/min are the maximum and minimum values in the array. The binary search runs O(log(max - min)) iterations (at most ~30 for values up to 10^9), and each iteration scans the array in O(n). - Space Complexity: O(1). Only a few variables for the binary search bounds and the feasibility check counters.