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 <= nThis 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.
JavaScript
Java
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.
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.
C++
Time Complexity: O(n log(max(bloomDay))) as it checks each day incrementally
Space Complexity: O(1)
| 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 |
BS-13. Minimum days to make M bouquets | Binary Search • take U forward • 199,550 views views
Watch 9 more video solutions →Practice Minimum Number of Days to Make m Bouquets with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor