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 <= nThe key challenge in #1482 Minimum Number of Days to Make m Bouquets is determining the earliest day when it becomes possible to create m bouquets, each requiring k adjacent flowers. Instead of simulating day-by-day growth, an efficient strategy is to apply Binary Search on the answer.
First, observe that the minimum possible day is the smallest value in the bloomDay array, while the maximum is the largest value. For any candidate day, we can scan the array and greedily count how many bouquets can be formed using flowers that have bloomed on or before that day. If we can form at least m bouquets, the day might be valid, and we attempt to find a smaller one.
This feasibility check runs in linear time, making the overall solution efficient. Binary search reduces the search space of days while the validation step ensures bouquet adjacency constraints are respected. The approach avoids brute-force simulation and works well for large inputs.
Time Complexity: O(n log D), where D is the range of days. Space Complexity: O(1).
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Binary Search with Greedy Feasibility Check | O(n log D) | O(1) |
| Brute Force Day Simulation | O(n * D) | O(1) |
take U forward
Use these hints if you're stuck. Try solving on your own first.
If we can make m or more bouquets at day x, then we can still make m or more bouquets at any day y > x.
We can check easily if we can make enough bouquets at day x if we can get group adjacent flowers at day x.
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.
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.
1function minDays(bloomDay, m, k) {
2 const canMakeBouquets = (days) => {
3 let bouquets = 0, flowers = This JavaScript solution is similar to the Python version, using binary search to find the minimum day. It involves a helper function 'canMakeBouquets' that checks if the required bouquets can be formed by day 'mid' during the binary search process.
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.
Time Complexity: O(n log(max(bloomDay))) as it checks each day incrementally
Space Complexity: O(1)
1#include <stdio.h>
2#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem reflects a common interview pattern combining binary search on the answer with greedy validation. Variations of this technique frequently appear in interviews at companies like Google, Amazon, and Meta.
Binary search works because the feasibility condition is monotonic. If it is possible to make m bouquets on a certain day, it will also be possible on any later day. This property allows us to efficiently narrow down the minimum valid day.
The problem mainly relies on arrays and simple counters. No complex data structure is required; a linear scan with counters is enough to track consecutive bloomed flowers and count valid bouquets.
The optimal approach uses binary search on the number of days. For each candidate day, we scan the array to check if enough bouquets can be formed using adjacent flowers that have bloomed by that day. This reduces the search space and achieves O(n log D) time complexity.
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.