Minimum Number of Days to Make m Bouquets - Solution & Explanation
Problem Statement
You are given an integer array bloomDay, an integer m and an integer k.
You want to make m bouquets. To make a bouquet, you need to use k adjacent flowers from the garden.
The garden consists of n flowers, the ith flower will bloom in the bloomDay[i] and then can be used in exactly one bouquet.
Return the minimum number of days you need to wait to be able to make m bouquets from the garden. If it is impossible to make m bouquets return -1.
Example 1:
Input: bloomDay = [1,10,3,10,2], m = 3, k = 1 Output: 3 Explanation: Let us see what happened in the first three days. x means flower bloomed and _ means flower did not bloom in the garden. We need 3 bouquets each should contain 1 flower. After day 1: [x, _, _, _, _] // we can only make one bouquet. After day 2: [x, _, _, _, x] // we can only make two bouquets. After day 3: [x, _, x, _, x] // we can make 3 bouquets. The answer is 3.
Example 2:
Input: bloomDay = [1,10,3,10,2], m = 3, k = 2 Output: -1 Explanation: We need 3 bouquets each has 2 flowers, that means we need 6 flowers. We only have 5 flowers so it is impossible to get the needed bouquets and we return -1.
Example 3:
Input: bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3 Output: 12 Explanation: We need 2 bouquets each should have 3 flowers. Here is the garden after the 7 and 12 days: After day 7: [x, x, x, x, _, x, x] We can make one bouquet of the first three flowers that bloomed. We cannot make another bouquet from the last three flowers that bloomed because they are not adjacent. After day 12: [x, x, x, x, x, x, x] It is obvious that we can make two bouquets in different ways.
Constraints:
bloomDay.length == n1 <= n <= 1051 <= bloomDay[i] <= 1091 <= m <= 1061 <= k <= n
Approach Overview
Problem Overview: You are given an array bloomDay where each value represents the day a flower blooms. The goal is to make m bouquets, each requiring k adjacent flowers. The task is to return the minimum number of days required so that at least m bouquets can be formed.
Approach 1: Greedy Sequential Day Simulation (O(n * D) time, O(1) space)
This approach simulates the garden day by day. Start from day 1 and keep increasing the day until the required bouquets can be formed. For each day, iterate through the array and count consecutive flowers whose bloom day is less than or equal to the current day. Every time you reach k consecutive flowers, increment the bouquet count and reset the counter. If the bouquet count reaches m, that day is the answer. While easy to implement, the algorithm may check many days up to the maximum bloom day, making it inefficient for large ranges.
Approach 2: Binary Search on Days (O(n log D) time, O(1) space)
The key insight: if it is possible to make m bouquets on day d, then it will also be possible on any later day. This monotonic property makes the problem ideal for binary search. Search the answer in the range between the minimum and maximum bloom days. For each candidate day, run a greedy check by scanning the array and counting consecutive bloomed flowers. Whenever k adjacent flowers are available, form a bouquet and reset the counter. If you can form at least m bouquets, move the search left to minimize the day; otherwise move right.
This approach avoids checking every day and instead narrows the search range logarithmically. The bouquet counting step is essentially a greedy scan because you always form a bouquet as soon as k adjacent flowers are available.
Recommended for interviews: Binary Search on Days is the expected solution. The brute-force simulation demonstrates the problem mechanics, but the optimized binary search shows that you recognized the monotonic feasibility condition and reduced the search space efficiently.
Approach 1: Binary Search on Days
This approach uses binary search to efficiently determine the minimum number of days needed to make the required number of bouquets. By evaluating the feasibility of creating bouquets for a specific day, the search narrows down the smallest number of days possible.
The idea is to perform binary search between the minimum day and the maximum day in the bloomDay array. For each middle day value in the binary search, check if it's possible to make the required number of bouquets within those days. This check involves iterating through the bloomDay array and simulating the bouquet-making process.
If it's possible to make the bouquets on the current day or fewer, adjust the search range towards smaller values; otherwise, increase the range.
The Python solution uses a binary search function that tests possible day numbers. The helper function 'canMakeBouquets' determines if bouquets can be made within a certain number of days by iterating through the bloomDay array and counting eligible flowers and bouquets.
Code
Python
JavaScript
Java
Complexity
Time Complexity: O(n log(max(bloomDay))) where n is the length of the bloomDay array. This is due to binary searching over the day range and checking each day.
Space Complexity: O(1) since no additional data structures proportional to input size are used.
Approach 2: Greedy Approach with Sequential Day Simulation
A more straightforward but less optimal approach is to simulate each day sequentially and check whether that day allows the creation of the necessary bouquets. This simulation checks for the day on each flower to see if the flower is usable and forms bouquets if possible. This approach refines checking for the earliest feasible day without having an initial constraint of possible day ranges.
This C solution iterates through each possible day, incrementing the number of bouquets built with adjacent flowers. It returns the minimum possible day when m bouquets can be successfully made, or -1 if impossible.
Complexity
Time Complexity: O(n log(max(bloomDay))) as it checks each day incrementally
Space Complexity: O(1)
Approach 3: Binary Search
According to the problem description, if a day t can satisfy making m bouquets, then for any t' > t, it can also satisfy making m bouquets. Therefore, we can use binary search to find the minimum day that satisfies making m bouquets.
Let mx be the maximum blooming day in the garden. Next, we define the left boundary of the binary search as l = 1 and the right boundary as r = mx + 1.
Then, we perform binary search. For each middle value mid = \frac{l + r}{2}, we check if it is possible to make m bouquets. If it is possible, we update the right boundary r to mid; otherwise, we update the left boundary l to mid + 1.
Finally, when l = r, the binary search ends. At this point, if l > mx, it means it is not possible to make m bouquets, and we return -1; otherwise, we return l.
Therefore, the problem is reduced to checking if a day days can make m bouquets.
We can use a function check(days) to determine if it is possible to make m bouquets. Specifically, we traverse each flower in the garden from left to right. If the blooming day of the current flower is less than or equal to days, we add the current flower to the current bouquet; otherwise, we clear the current bouquet. When the number of flowers in the current bouquet equals k, we increment the bouquet count and clear the current bouquet. Finally, we check if the bouquet count is greater than or equal to m. If it is, it means it is possible to make m bouquets; otherwise, it is not possible.
The time complexity is O(n times log M), where n and M are the number of flowers in the garden and the maximum blooming day, respectively. In this problem, M leq 10^9. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Binary Search on Days | Time Complexity: O(n log(max(bloomDay))) where n is the length of the bloomDay array. This is due to binary searching over the day range and checking each day. |
| Greedy Approach with Sequential Day Simulation | Time Complexity: O(n log(max(bloomDay))) as it checks each day incrementally |
| Binary Search | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Sequential Day Simulation | O(n * D) | O(1) | Useful for understanding the problem mechanics or when the day range is very small |
| Binary Search on Days | O(n log D) | O(1) | Optimal approach for large inputs where bloom days span a large range |
Video Solution
BS-13. Minimum days to make M bouquets | Binary Search • take U forward • 373,764 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum Number of Days to Make m Bouquets easy or hard?
Minimum Number of Days to Make m Bouquets Python/Java solution
How to solve Minimum Number of Days to Make m Bouquets in O(n log D)?
What is the best approach for Minimum Number of Days to Make m Bouquets?
Is Minimum Number of Days to Make m Bouquets asked at Google/Amazon/Meta?
What data structure is used in Minimum Number of Days to Make m Bouquets?
What is the time complexity of Minimum Number of Days to Make m Bouquets?
Ready to solve this problem?
Practice Minimum Number of Days to Make m Bouquets with our built-in code editor and test cases.
Practice on FleetCode