Minimum Number of Days to Make m Bouquets | Leetcode 1482 | Binary Search on Answers

The “Minimum Number of Days to Make m Bouquets” problem is a popular binary search interview question that tests your ability to optimize under constraints.

In this blog, we’ll explain the problem, walk you through both brute force and optimal solutions, and make everything easy to understand with code comments, dry runs, and clear explanations.

Here’s the [Problem Link] to begin with.

What Does the Problem Say?

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 == n
• 1 <= n <= 105
• 1 <= bloomDay[i] <= 109
• 1 <= m <= 106
• 1 <= k <= n

Brute Force Solution (Try Every Possible Day)

Intuition and Approach

Let’s solve the problem in the most straightforward way:

1. Try Every Day:
   Try every possible day from the earliest blooming flower to the latest.
2. Check If Bouquets Can Be Made:
   For each day, check if it is possible to make m bouquets, each with k adjacent flowers that have bloomed by that day.
3. Return the First Valid Day:
   The first day for which it’s possible is our answer.
4. Why does this work?
   We check every possible day, so we’re sure to find the minimum day that works.

This approach is easy to understand but not efficient for large inputs.

Code Implementation

from typing import List

class Solution:
    def canMakeBouquet(self, bloomDay: List[int], m: int, k: int, day: int) -> bool:
        bouquets = 0
        flowers = 0
        for bloom in bloomDay:
            if bloom <= day:
                flowers += 1
                if flowers == k:
                    bouquets += 1
                    flowers = 0
            else:
                flowers = 0
        return bouquets >= m

    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        n = len(bloomDay)
        if m * k > n:
            return -1  # Not enough flowers

        min_day = min(bloomDay)
        max_day = max(bloomDay)

        for day in range(min_day, max_day + 1):
            if self.canMakeBouquet(bloomDay, m, k, day):
                return day

        return -1

Code Explanation

• For each possible day from the earliest to the latest bloom, check if you can make the required bouquets.
• The helper function canMakeBouquet counts how many bouquets can be made by that day.
• If you find a day where it’s possible, return it.

Dry Run

Input:
bloomDay = [1], m = 3, k = 1

• Try day = 1: Only 1 flower has bloomed, not enough.
• Try day = 2: Two flowers have bloomed, still not enough.
• Try day = 3: Three flowers have bloomed (positions 0, 2, 4) → can make 3 bouquets.

Final Output:
3

Time and Space Complexity

• Time Complexity: O((max(bloomDay) – min(bloomDay)) * n)
  For each day, we scan the whole array.
• Space Complexity: O(1)
  Only variables for counting.

Conclusion

The brute force approach is simple and works for small inputs, but it’s too slow for large values.

Optimal Solution (Binary Search)

Intuition and Approach

We can do much better using binary search:

1. Binary Search on Days:
   The answer lies between the earliest and latest bloom days. Use binary search to find the minimum day.
2. Check If Bouquets Can Be Made:
   For each mid value (day), check if it’s possible to make m bouquets.
3. Adjust Search Window:
   • If it’s possible, try an earlier day.
   • If not, try a later day.
4. Why does this work?
   The function for checking if bouquets can be made is monotonic: as the day increases, it becomes easier to make bouquets. Binary search is perfect for this.

Code Implementation

from typing import List

class Solution:
    def canMakeBouquet(self, bloomDay: List[int], m: int, k: int, day: int) -> bool:
        total = 0
        count = 0
        for i in range(len(bloomDay)):
            if bloomDay[i] <= day:
                count += 1
                if count == k:
                    total += 1
                    count = 0
            else:
                count = 0
        return total >= m

    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m * k > len(bloomDay):
            return -1

        low, high = min(bloomDay), max(bloomDay)
        ans = -1

        while low <= high:
            mid = (low + high) // 2
            if self.canMakeBouquet(bloomDay, m, k, mid):
                ans = mid
                high = mid - 1
            else:
                low = mid + 1

        return ans

Code Explanation

• Use binary search between the earliest and latest bloom days.
• For each mid day, check if you can make the required bouquets.
• If you can, try a smaller day.
• If not, try a larger day.
• Return the minimum valid day found.

Dry Run

Input:
bloomDay = [1], m = 3, k = 1

• low = 1, high = 10
• mid = 5: Can make 3 bouquets? Yes → try smaller (high = 4)
• mid = 2: Can make 2 bouquets? No → try larger (low = 3)
• mid = 3: Can make 3 bouquets? Yes → try smaller (high = 2)

Loop ends, answer is 3.

Time and Space Complexity

• Time Complexity: O(n * log(max(bloomDay) – min(bloomDay)))
  Binary search on days, checking all flowers for each guess.
• Space Complexity: O(1)
  Only variables for counting.

Conclusion

The optimal solution is efficient and works well for large arrays and high values. It’s the best approach for interviews and practical use.

Final Thoughts

The “Minimum Number of Days to Make m Bouquets” problem is a great example of how to optimize from brute force to an efficient binary search solution. Start with brute force to understand the basics, then use binary search for best performance.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.