In this article, we will delve into solving the problem of finding the minimum number of days required to make m bouquets from a given garden, where each bouquet requires k adjacent flowers to bloom. We will explore both a brute force approach and a highly efficient approach using Binary Search.
If you’re just joining us, it might be helpful to catch up on the previous entries. Want to see more problem-solving techniques? Follow me here on my blog!
Understanding the Problem
We are given an integer array bloomDay, an integer m, and an integer k. We need to determine the minimum number of days required to make m bouquets, each consisting of k adjacent flowers. If it’s impossible to make the required number of bouquets, we should 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.
Brute Force Approach
The brute force approach involves checking each day sequentially, starting from the earliest possible day, and counting the number of bouquets that can be formed on each day. This method is straightforward but inefficient for large inputs due to its high time complexity.
def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
n = len(bloomDay)
if m * k > n:
return -1
max_day = max(bloomDay)
for day in range(1, max_day + 1):
bouquets = 0
flowers = 0
for i in range(n):
if bloomDay[i] <= day:
flowers += 1
if flowers == k:
bouquets += 1
flowers = 0
else:
flowers = 0
if bouquets >= m:
return day
return -1
Explanation
- Initial Checks: Check if it’s possible to make m bouquets given the total number of flowers (
n). Ifm * k > n, return-1. - Iterate Through Each Day: Iterate from day 1 to the maximum day in
bloomDay. - Count Bouquets for Each Day:
- For each day, count the number of bouquets that can be formed.
- Reset the flower count if a flower hasn’t bloomed yet or if a bouquet is completed.
- Return the Minimum Day: Return the first day where the required number of bouquets can be formed.
Time Complexity: O(n * d), where n is the length of bloomDay and d is the range of days max(bloomDay).
Space Complexity: O(1), as we only use a fixed amount of additional space.
Using Efficient Approach: Binary Search
The naive way of solving this problem is to iterate over each day sequentially, starting from day 1, and check if it’s possible to make the required number of bouquets. However, this approach is inefficient and impractical for large inputs. Instead, we can utilize the fact that the number of bloomed flowers on a given day is a monotonically increasing function. This means that once a flower blooms, it stays bloomed for all subsequent days.
Given this property, we can use binary search to efficiently find the minimum number of days needed. By setting our search range between the smallest and largest values in bloomDay, we can repeatedly narrow down the range until we find the solution.
def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
def isValid(x):
total = 0
currcount = 0
for b in bloomDay:
if x >= b:
currcount += 1
else:
total += currcount // k
if total >= m:
return True
currcount = 0
total += currcount // k
return total >= m
if m * k > len(bloomDay):
return -1
left = min(bloomDay)
right = max(bloomDay)
while left < right:
mid = left + (right - left) // 2
if isValid(mid):
right = mid
else:
left = mid + 1
return left
Explanation
- Helper Function isValid(x):
- This function checks if it’s possible to make
mbouquets by dayx. - It iterates through
bloomDay, counting consecutive bloomed flowers. - If the count of consecutive bloomed flowers reaches
k, it increments the total bouquet count. - If the total bouquet count reaches
m, the function returnsTrue.
- This function checks if it’s possible to make
- Binary Search Logic:
- Initialize
leftto the minimum value inbloomDayandrightto the maximum value. - Use binary search to find the minimum day where
isValid(day)returnsTrue. - Adjust the search range based on the result of
isValid(mid).
- Initialize
Time Complexity: O(n log d), where n is the length of bloomDay and d is the range of days max(bloomDay) - min(bloomDay).
Space Complexity: O(1), as we only use a fixed amount of additional space.
Conclusion
In this article, we’ve tackled the problem of finding the minimum number of days required to make m bouquets with k adjacent flowers using both a brute force approach and an efficient binary search approach. While the brute force solution is simple to implement, the binary search method significantly reduces the time complexity, making it suitable for large inputs.
Understanding these methods enhances your problem-solving skills and prepares you for tackling similar challenges in coding interviews and competitions.
Found this helpful? Follow me for more leetcode adventures! Questions? React out via email.
