Minimum Number of Days to Make m Bouquets

Medium

Asked by:

+3

More companies

27 views

Topics:

ArraysBinary Search

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.

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 <= 10⁵
1 <= bloomDay[i] <= 10⁹
1 <= m <= 10⁶
1 <= k <= n

Try coding it in LeetCode

Minimum Number of Days to Make m Bouquets

Medium

Asked by:

27 views

Topics:

ArraysBinary Search

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.

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 <= 10⁵
1 <= bloomDay[i] <= 10⁹
1 <= m <= 10⁶
1 <= k <= n

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the upper and lower bounds for the number of flowers in `bloomDay` (n), the number of bouquets to make (m), and the number of adjacent flowers required per bouquet (k)?
Can the values in the `bloomDay` array be zero or negative? What is the maximum value in `bloomDay`?
If it's impossible to make `m` bouquets with the given `bloomDay` and `k`, what value should I return? Should I return -1, or throw an exception?
If there are multiple days that satisfy the condition of being the minimum number of days, can I return any one of those days?
Is k always less than or equal to the length of bloomDay?

Brute Force Solution

Approach

The brute force approach to finding the minimum number of days involves checking every possible number of days to see if we can make the required number of bouquets. We essentially test each day value one by one until we find the smallest one that works. It's like trying every number until we hit the right one.

Here's how the algorithm would work step-by-step:

Start by considering the smallest possible number of days it might take.
For that number of days, check if you can create the required number of bouquets by only using flowers that have bloomed by that day, and that are next to each other in the right sequence.
If you can make enough bouquets with that number of days, we might have found our answer, but we need to check if there is any number of days less than that which also could work.
If you can't make enough bouquets, increase the number of days by one and repeat the process.
Keep increasing the number of days and checking if you can make the required number of bouquets each time.
Continue this process until you find the smallest number of days for which you can create the required number of bouquets.

Code Implementation

def min_days_make_bouquets_brute_force(bloom_day, number_of_bouquets, flowers_per_bouquet):
    days = 1
    max_days = max(bloom_day)

    while days <= max_days:
        # Check if we can make the required bouquets with 'days'
        possible = can_make_bouquets(bloom_day, days, number_of_bouquets, flowers_per_bouquet)

        if possible:
            return days

        days += 1

    return -1

def can_make_bouquets(bloom_day, current_day, number_of_bouquets, flowers_per_bouquet):
    bouquets_made = 0
    flowers_collected = 0

    for bloom_value in bloom_day:
        if bloom_value <= current_day:
            flowers_collected += 1
            if flowers_collected == flowers_per_bouquet:
                bouquets_made += 1
                flowers_collected = 0
        else:
            flowers_collected = 0

    # Check if we have made enough bouquets
    if bouquets_made >= number_of_bouquets:
        return True
    else:
        return False

def min_days_to_make_m_bouquets(bloom_day, number_of_bouquets, flowers_per_bouquet):
    if number_of_bouquets * flowers_per_bouquet > len(bloom_day):
        return -1

    min_possible_day = min(bloom_day)
    # Start checking from the minimum possible bloom day.
    for day_to_check in range(min_possible_day, max(bloom_day) + 1):
        if can_make_bouquets(bloom_day, day_to_check, number_of_bouquets, flowers_per_bouquet):

            # Found a possible day to make the bouquets.
            return day_to_check
    return -1

Big(O) Analysis

Time Complexity

O(n*m) – The brute force approach iterates through a range of possible days from the minimum bloom day to the maximum bloom day (which could be considered 'n' in the worst case where n is the range of possible days and is dependent on the size of the input array). For each possible number of days, the algorithm checks if it's possible to make 'm' bouquets. In the worst case, this check involves iterating through the entire bloomDay array to find consecutive sequences of bloomed flowers and count the possible bouquets, which takes O(n) time where n is the length of bloomDay array. Since we iterate through potentially all possible days and for each day check if we can make the required number of bouquets which takes O(n), the overall time complexity becomes O(n*m) where n is the length of bloomDay array and m is the range of possible bloom days to check.

Space Complexity

O(1) – The provided brute force algorithm checks each possible number of days. It doesn't involve creating any auxiliary data structures that scale with the input size N (where N is the number of flowers). It only uses a few variables to track the current number of days and potentially a counter while checking for bouquets. Therefore, the auxiliary space complexity is constant.

Optimal Solution

Approach

The optimal strategy avoids checking every possible combination of days. Instead, we use a process of elimination guided by the fact that the number of days must be within a certain range. This allows us to efficiently narrow down the possibilities to find the minimum number of days required.

Here's how the algorithm would work step-by-step:

First, figure out the earliest and latest possible days when you could make bouquets. The earliest is when all flowers bloom on the same day, and the latest is when each flower blooms on a different day.
Pick a day in the middle of this range. Check if it's possible to make the required number of bouquets by this day. To do this, go through the flowers, see how many bouquets you can make if flowers only bloom on or before this day.
If you can make enough bouquets by this day, that means the minimum number of days is somewhere between the earliest day and the day you just checked. Try a day in the middle of that new, smaller range.
If you can't make enough bouquets by the day you checked, that means the minimum number of days is somewhere between the day you checked and the latest possible day. Try a day in the middle of this other new, smaller range.
Keep narrowing the range like this, always checking the middle day, until you find the smallest number of days that allows you to make the required number of bouquets.

Code Implementation

def min_days_to_make_m_bouquets(bloom_day, number_of_bouquets, flowers_per_bouquet):
    number_of_flowers = len(bloom_day)
    if number_of_bouquets * flowers_per_bouquet > number_of_flowers:
        return -1

    minimum_bloom_day = min(bloom_day)
    maximum_bloom_day = max(bloom_day)

    while minimum_bloom_day < maximum_bloom_day:
        mid_day = (minimum_bloom_day + maximum_bloom_day) // 2
        
        #Check if it's possible to create enough bouquets
        if can_make_bouquets(bloom_day, mid_day, number_of_bouquets, flowers_per_bouquet):
            maximum_bloom_day = mid_day
        else:
            minimum_bloom_day = mid_day + 1

    return minimum_bloom_day

def can_make_bouquets(bloom_day, current_day, number_of_bouquets, flowers_per_bouquet):
    bouquets_made = 0
    flowers_collected = 0

    for day in bloom_day:
        if day <= current_day:
            flowers_collected += 1

            if flowers_collected == flowers_per_bouquet:
                bouquets_made += 1
                flowers_collected = 0
        else:
            flowers_collected = 0

    # Return True if we have made enough bouquets to fulfill the requirement
    return bouquets_made >= number_of_bouquets

Big(O) Analysis

Time Complexity

O(n log m) – The algorithm uses binary search to find the minimum number of days, where m represents the range between the earliest and latest possible bloom days. For each day (potential solution) considered in the binary search, we iterate through the bloomday array of size n to check if we can make the required number of bouquets. The binary search takes log m steps, and the check within each step takes O(n) time. Therefore, the overall time complexity is O(n log m), where n is the number of flowers and m is the range of possible bloom days.

Space Complexity

O(1) – The algorithm primarily uses binary search to find the minimum number of days. It involves calculations using variables like the current middle day, the earliest day, and the latest day. These variables consume constant extra space regardless of the number of flowers or bouquets. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Empty bloomDay array or invalid input (m or k <= 0)	Return -1 immediately as no bouquets can be formed with invalid input or no flowers.
m * k exceeds the length of bloomDay	Return -1 immediately because it's impossible to create the required number of bouquets.
bloomDay array contains only one element	Return the bloomDay if m and k are both 1, otherwise -1.
All bloomDay values are the same	Binary search should still converge to the correct minimum day if a valid solution exists, otherwise return -1 if no solution.
No possible solution exists (e.g., bloomDay values are too large)	Binary search will converge where left > right, indicating no solution; return -1.
bloomDay array contains very large numbers potentially causing integer overflow in calculations	Ensure binary search mid calculation uses long or appropriate data type to prevent overflow.
bloomDay array is sorted in descending order (worst case for some inefficient algorithms)	Binary search efficiency is unaffected by the order of bloomDay values because it only cares about minimum and maximum possible bloom days and checking for existence of valid bloom day within that range.
Extreme values for m and k within the problem constraints (e.g., m = 1, n = 10^5, k = 10^5)	Binary search should handle large array sizes efficiently with O(log(max(bloomDay))) time complexity.

Empty bloomDay array or invalid input (m or k <= 0)

How to Handle:

Return -1 immediately as no bouquets can be formed with invalid input or no flowers.

m * k exceeds the length of bloomDay

How to Handle:

Return -1 immediately because it's impossible to create the required number of bouquets.

bloomDay array contains only one element

How to Handle:

Return the bloomDay if m and k are both 1, otherwise -1.

All bloomDay values are the same

How to Handle:

Binary search should still converge to the correct minimum day if a valid solution exists, otherwise return -1 if no solution.

No possible solution exists (e.g., bloomDay values are too large)

How to Handle:

Binary search will converge where left > right, indicating no solution; return -1.

bloomDay array contains very large numbers potentially causing integer overflow in calculations

How to Handle:

Ensure binary search mid calculation uses long or appropriate data type to prevent overflow.

bloomDay array is sorted in descending order (worst case for some inefficient algorithms)

How to Handle:

Binary search efficiency is unaffected by the order of bloomDay values because it only cares about minimum and maximum possible bloom days and checking for existence of valid bloom day within that range.

Extreme values for m and k within the problem constraints (e.g., m = 1, n = 10^5, k = 10^5)

How to Handle:

Binary search should handle large array sizes efficiently with O(log(max(bloomDay))) time complexity.