We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Days to Make m Bouquets

Difficulty: Medium

Problem Description

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 i-th 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.

Key Insights

  • Each bouquet requires k adjacent flowers.
  • The blooming of flowers is determined by the values in the bloomDay array.
  • We can use binary search to efficiently determine the minimum number of days required.
  • We need to check if it is possible to create the required m bouquets on or before a given day.

Space and Time Complexity

Time Complexity: O(n log(max(bloomDay)))
Space Complexity: O(1)

Solution

To solve this problem, we will employ a binary search approach on the number of days. The algorithm works as follows:

  1. Binary Search Setup: Establish the search range for the minimum days, starting from the minimum value in bloomDay to the maximum value in bloomDay.
  2. Feasibility Check: For a mid-point day during the binary search, check if it is possible to create m bouquets with k adjacent flowers that have bloomed by this day.
  3. Count Bouquets: Iterate through the bloomDay array, counting how many bouquets can be formed by keeping track of consecutive flowers that have bloomed by the given day.
  4. Adjust Search Range: If m bouquets can be formed by the mid-point day, try to find a smaller number of days; otherwise, increase the search range.

Code Solutions

def minDays(bloomDay, m, k):
    if m * k > len(bloomDay):
        return -1

    def canMakeBouquets(days):
        bouquets = 0
        count = 0
        for bloom in bloomDay:
            if bloom <= days:
                count += 1
                if count == k:
                    bouquets += 1
                    count = 0
            else:
                count = 0
        return bouquets >= m

    left, right = min(bloomDay), max(bloomDay)
    while left < right:
        mid = (left + right) // 2
        if canMakeBouquets(mid):
            right = mid
        else:
            left = mid + 1
    return left
← Back to All Questions