< Back





1482. Minimum Number of Days to Make m Bouquets

We're given a list of when flowers in a garden bloom, bloomDay, a number of bouquets requested, m,
and the number of flowers required in each bouquet, k. We can only pick flowers on the day they
bloom or after. We also can only put adjacent flowers in a given bouquet. We're asked to find the
minimum or first day in which we can satisfy the request to create m bouquets of k flowers each.

We use binary search, where our search space is the minimum and maximum bloom days. For a selected
bloomDay, mid, we check how many bouquets we can make with k flowers each. If a flower,
bloomDay[i], is less than or equal to mid, we increment the count of flowers in the current bouquet.
Otherwise, we reset the number of flowers in the bouquet to 0. If we can grab k adjacent flowers to
create the bouquet, we increment the count of bouquets and reset our flowers count.

If the number of bouquets we created is greater than or equal to m, we know that we've waited too
long, and we can probably create the bouquet on an earlier day - thus we set r = mid - 1. Otherwise,
if we can't make the bouquet, we know we aren't waiting long enough, so we set l = mid + 1.

Eventually, l greater than r, and l will be the minimum day we can create m bouquets of k flowers.

The solution is as follows:


  class Solution:
      def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
          n = len(bloomDay)

          if n < m * k:
              return -1

          l, r = min(bloomDay), max(bloomDay)

          while l <= r:
              mid = (r + l) // 2
              bouquets = flowers = 0

              for i in range(n):
                  if bloomDay[i] <= mid:
                      flowers += 1
                  else:
                      flowers = 0

                  if flowers == k:
                      bouquets += 1
                      flowers = 0

              if bouquets >= m:
                  r = mid - 1
              else:
                  l = mid + 1

          return l


_ Time Complexity:

  O(n log(m)) - Where n is the number of flowers and m is the maximum bloom day.

_ Space Complexity:

  O(1) - We use constant space to conduct the search.