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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Days to Make m Bouquets

Number: 1605

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Microsoft, Bloomberg, Meta, Navi

Problem Description

Given an array where each element represents the day a specific flower blooms, determine the minimum number of days required to make m bouquets. Each bouquet requires k consecutive bloomed flowers from the garden. If it is impossible to form m bouquets, return -1.

Key Insights

  • Use binary search on the range of possible days since waiting more days only increases the number of available flowers.
  • At each day guess, simulate whether it is possible to form m bouquets by iterating over the bloomDay array.
  • Count only bouquets formed by k consecutive flowers (reset count when encountering a flower that hasn't bloomed by the considered day).
  • Early termination: if the total number of flowers is insufficient to form m bouquets (i.e. if m * k > n), return -1 immediately.

Space and Time Complexity

Time Complexity: O(n * log(max(bloomDay))) - For each binary search iteration, we scan the entire array. Space Complexity: O(1) - Constant extra space is used.

Solution

The problem can be efficiently solved using a binary search approach. The idea is to determine a minimum day such that there are enough adjacent flowers (k consecutive ones) to form m bouquets. We define a helper function to check if for a given day, at least m bouquets are possible.

The binary search is performed over the range of days [min(bloomDay), max(bloomDay)]. For each mid value (representing a day), iterate through the bloomDay array to count how many bouquets can be created if only flowers with bloomDay <= mid are considered bloomed. The count resets if a flower that hasn't bloomed is encountered. If the bouquet count meets or exceeds m, then this day is a potential answer, and we try to find a smaller day. Otherwise, we search in the higher day range.

Data structures used include simple counters and pointers for iterating over the array. The algorithmic approach is a combination of greedy checking and binary search.

Code Solutions

# Python solution for the problem

def minDays(bloomDay, m, k):
    # If total flowers are less than required, return -1 early
    if m * k > len(bloomDay):
        return -1

    # Helper function to check if we can make required bouquets by day "day"
    def canMakeBouquets(day):
        bouquets = 0      # Number of bouquets made so far
        consecutive = 0   # Count of consecutive blooming flowers
        for bloom in bloomDay:
            # If the flower blooms by the given day, increase consecutive count
            if bloom <= day:
                consecutive += 1
                # If we reached k consecutive flowers, one bouquet is formed
                if consecutive == k:
                    bouquets += 1
                    consecutive = 0  # Reset for the next bouquet
            else:
                consecutive = 0  # Reset count if flower not bloomed
            # Early return if required bouquets have been made
            if bouquets >= m:
                return True
        return False

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

    # Binary search on the day range
    while low <= high:
        mid = (low + high) // 2  # middle day value
        if canMakeBouquets(mid):
            result = mid  # candidate answer
            high = mid - 1  # try to find a smaller day
        else:
            low = mid + 1  # need more days
    return result

# Example Test Cases
print(minDays([1,10,3,10,2], 3, 1))  # Expected output: 3
print(minDays([1,10,3,10,2], 3, 2))  # Expected output: -1
print(minDays([7,7,7,7,12,7,7], 2, 3))  # Expected output: 12
← Back to All Questions