Skip to main content

Binary Search

Minimum Number of Days to Make m Bouquets Solution In C++/Java/Python/JS

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.
Minimum Number of Days to Make m Bouquets-problem description

Examples:

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.

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.

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 2 bouquets in different ways.

Constraints:

bloomDay.length == n
1 <= n <= 10⁵
1 <= bloomDay[i] <= 10⁹
1 <= m <= 10⁶
1 <= k <= n

Brute Force Approach

To approach the problem, we are given an integer array bloomDay, an integer m, and an integer k, and we need to determine the minimum number of days required to make m bouquets, where each bouquet consists of k adjacent flowers.

Our goal is to find the minimum number of days we need to wait so that we can form m bouquets using the flowers that have bloomed by that day. If it is impossible to make m bouquets, we return -1.

First, what can be the minimum number of days needed?

The minimum number of days required should be equal to the earliest blooming flower, i.e., min(bloomDay). This is because if we try to make bouquets before this day, we will not have any flowers bloomed.

Now that we know the minimum days, what would be the maximum number of days?

The maximum number of days required should be the latest blooming flower, i.e., max(bloomDay). This is because, by this time, all flowers would have bloomed, and we can check if forming m bouquets is possible.

Thus, our search space for the answer ranges from min(bloomDay) to max(bloomDay). Now, the problem reduces to finding the minimum number of days such that we can form m bouquets.

A basic approach is to iterate through all possible days from min(bloomDay) to max(bloomDay) and check whether it is possible to form m bouquets on that day. If it is possible, then it is a valid solution; otherwise, we increase the number of days and check again. We continue this process until we find the minimum day that allows us to form m bouquets.

Since the range from min(bloomDay) to max(bloomDay) covers all possible days, starting from the minimum and stopping at the first valid day will give us the desired result.

Consider the example with bloomDay = [1,10,3,10,2] and m = 3, k = 1.
We start by taking the minimum blooming day, which is 1, as the smallest possible day to form bouquets, and maximum blooming day, which is 10, as the largest possible day.

We then check how many bouquets we can make on each of these days:

  • For day = 1, we can make 1 bouquet, which is less than m = 3, so it doesn't work.
  • For day = 2, we can make 2 bouquets, still less than m = 3, so it doesn't work.
  • For day = 3, we can make 3 bouquets, which meets the requirement.
  • For day = 4, we can make 3 bouquets, which meets the requirement.

Since 3 is the first day where we can form m = 3 bouquets, it is the minimum number of days required.

So, the answer is 3.

Let's call the smallest number of days needed to form m bouquets as ans.
Any day between the minimum possible day (min(bloomDay)) and ans - 1 won't work because it will always result in fewer than m bouquets.
However, any day from ans to the maximum possible day (max(bloomDay)) will allow us to form at least m bouquets.

Therefore, ans is the smallest number of days required to make m bouquets, and we return ans as the answer.

Minimum Number of Days to Make m Bouquets-example

How Can We Determine if a Given Day is Valid?

Imagine you have a garden where each flower blooms on a specific day. Your goal is to make m bouquets, and each bouquet must have exactly k adjacent bloomed flowers. However, the flowers bloom on different days, so you need to determine whether, by a given day, you can collect enough adjacent flowers to form the required bouquets.

To achieve this, we simulate the process of picking flowers as they bloom and grouping them into bouquets.

  1. Initializing Counters:
    Imagine you're walking through the garden with a basket, collecting flowers for a bouquet. You need to gather exactly k flowers in a row before you can tie them into a bouquet. So, you keep track of how many flowers you have picked continuously.
    Real-world connection:
    • We start by setting bouquetCount = 0 to keep track of how many bouquets we have successfully made.
    • We also initialize flowersInARow = 0 to count consecutive bloomed flowers as we traverse the garden.
  2. Traversing the Flowerbed:Real-world connection:
    As you move along the garden, you inspect each flower. If it has bloomed, you pick it; if it hasn't, you can't use it yet.
    • We go through each flower one by one in bloomDay, checking if it has bloomed by the given day.
  3. Checking if a Flower Has Bloomed (bloomDay[i] ≤ day):
    If a flower is fresh and open, you pluck it and add it to your basket, increasing your flower count.
    Real-world connection:
    • If a flower has bloomed on or before the given day, it is ready to be picked, so we increase flowersInARow by 1.
  4. Forming a Bouquet (flowersInARow == k):
    As soon as you have exactly k flowers in your hands, you tie them together into a bouquet and place them aside. Since each bouquet must have its own set of k adjacent flowers, you reset your count and start fresh for the next bouquet.
    Real-world connection:
    • Once we have gathered k consecutive bloomed flowers, we form a bouquet.
    • We then increase bouquetCount by 1 because we have successfully made a bouquet.
    • We reset flowersInARow = 0 to start counting again for the next bouquet.
  5. Encountering a Non-Bloomed Flower (bloomDay[i] > day):
    Imagine walking through the garden and suddenly encountering a flower bud that hasn’t opened yet. You can’t use it in a bouquet, so you discard any partial collection of flowers and start looking for a new set of adjacent bloomed flowers.
    Real-world connection:
    • If we reach a flower that hasn’t bloomed yet, we reset flowersInARow to 0.
    • This is because flowers in a bouquet must be adjacent, and a non-bloomed flower breaks the chain.
  6. Continuing Until We Form m Bouquets or Reach the End:
    You continue picking and tying flowers into bouquets until either:
    • We keep going until we reach the end of the flowerbed or successfully form m bouquets (bouquetCount >= m).
    • If we have made at least m bouquets, the given day is valid.
      Real-world connection:
    • You’ve made enough bouquets (success!).
    • You’ve walked through the entire garden but couldn’t make m bouquets (failure—need more days for flowers to bloom).
💡
Try it Yourself!

Let's understand with an example:

Let's do a concise dry run for bloomDay = [3,3,3,3,5,3,3], m = 2, k = 3 using the linear search approach.

Step 1: Identify Search Range

  • Minimum bloom day = min(bloomDay) = 3
  • Maximum bloom day = max(bloomDay) = 5
  • We need to find the smallest day where we can make m = 2 bouquets, each using k = 3 adjacent flowers.

Step 2: Checking for Valid DaysDay = 3:

  • Bloomed garden: [✔, ✔, ✔, ✔, ✘, ✔, ✔]
  • Checking for k = 3 adjacent bloomed flowers:
    • First three flowers (✔✔✔) → 1 bouquet
    • Fourth flower is also bloomed (✔) → Extend but already counted
    • Fifth flower (✘) → Reset count
    • Last two flowers (✔✔) → Not enough for another bouquet
  • Total bouquets = 1 (less than m = 2) → Not valid

Day = 4:

  • Same result as day 3 since no new flowers bloom → Not valid

Day = 5:

  • Bloomed garden: [✔, ✔, ✔, ✔, ✔, ✔, ✔]
  • Checking for k = 3 adjacent bloomed flowers:
    • First three flowers (✔✔✔) → 1 bouquet
    • Next three flowers (✔✔✔) → 2nd bouquet
  • Total bouquets = 2 (m = 2) → Valid day

Conclusion

The minimum number of days required to form m = 2 bouquets is 5.
Output: 5

Steps to Implement the Solution:

Define the Helper Function (daysPossible):
Initialize a bouquetCount to track the number of bouquets made.
Use a flowersInARow counter to track consecutive bloomed flowers.
Iterate through the bloomDay array:
If the flower blooms on or before the given day, increment flowersInARow.
If not, reset flowersInARow.
When flowersInARow reaches k, increment the bouquetCount and reset flowersInARow.
If bouquetCount is greater than or equal to m, return true, indicating that it's possible to make m bouquets; otherwise, return false.

Find the Range for the Number of Days:
Initialize start as the minimum bloom day in the bloomDay array.
Initialize end as the maximum bloom day in the bloomDay array.

Iterate Over All Possible Days:
Iterate through all possible days from start to end:
For each day i, use the daysPossible function to check if it is possible to form m bouquets.
If it is possible to form m bouquets on day i, return i as the answer (minimum day required).

Return the Result:
If no valid day is found after checking all possible days, return -1, indicating that it's impossible to form m bouquets.

Code Implementation
1. C++ Try on Compiler 
class Solution {
    // Function to check if it is possible to make 'm' bouquets on a given 'day'
    bool daysPossible(vector<int>& bloomDay, int day, int k, int m)
    {   
        int bouquetCount = 0;
        int flowersInARow = 0;

        // Iterate through each flower's bloom day
        for(auto &bday: bloomDay)
        {
            // Check if the flower blooms on or before the given day
            if(bday <= day)
                flowersInARow++;
            else
                flowersInARow = 0;
            
            // If we have 'k' consecutive bloomed flowers, make a bouquet
            if(flowersInARow == k)
            {
                flowersInARow = 0;
                bouquetCount++;
            }
        }

        // Return true if we can make at least 'm' bouquets
        return bouquetCount >= m;
    }
public:
    // Function to find the minimum number of days required
    int minDays(vector<int>& bloomDay, int m, int k) {
        int mindays = -1;

        // Set the starting day as the minimum bloom day in the array
        int start = *min_element(bloomDay.begin(), bloomDay.end());

        // Set the ending day as the maximum bloom day in the array
        int end = *max_element(bloomDay.begin(), bloomDay.end());

        // Iterate through all possible days from minimum to maximum bloom day
        for(int i=start; i <= end; i++)
        {
            // If making 'm' bouquets is possible on day 'i', return 'i'
            if(daysPossible(bloomDay, i, k, m))
            {
                return i;
            }
        }

        // If no valid day is found, return -1
        return mindays;
    }
};

2. Java Try on Compiler 
import java.util.*;

class Solution {
    // Function to check if it is possible to make 'm' bouquets on a given 'day'
    private boolean daysPossible(int[] bloomDay, int day, int k, int m) {
        int bouquetCount = 0;
        int flowersInARow = 0;

        // Iterate through each flower's bloom day
        for(int bday : bloomDay) {
            // Check if the flower blooms on or before the given day
            if(bday <= day)
                flowersInARow++;
            else
                flowersInARow = 0;

            // If we have 'k' consecutive bloomed flowers, make a bouquet
            if(flowersInARow == k) {
                flowersInARow = 0;
                bouquetCount++;
            }
        }

        // Return true if we can make at least 'm' bouquets
        return bouquetCount >= m;
    }

    // Function to find the minimum number of days required
    public int minDays(int[] bloomDay, int m, int k) {
        int mindays = -1;

        // Set the starting day as the minimum bloom day in the array
        int start = Arrays.stream(bloomDay).min().getAsInt();

        // Set the ending day as the maximum bloom day in the array
        int end = Arrays.stream(bloomDay).max().getAsInt();

        // Iterate through all possible days from minimum to maximum bloom day
        for(int i = start; i <= end; i++) {
            // If making 'm' bouquets is possible on day 'i', return 'i'
            if(daysPossible(bloomDay, i, k, m)) {
                return i;
            }
        }

        // If no valid day is found, return -1
        return mindays;
    }
}

3. Python Try on Compiler 
class Solution(object):
    def days_possible(self, bloomDay, day, k, m):
        """
        Helper function to check if it is possible to make 'm' bouquets on a given 'day'.
        """
        bouquet_count = 0
        flowers_in_a_row = 0

        # Iterate through each flower's bloom day
        for bday in bloomDay:
            # Check if the flower blooms on or before the given day
            if bday <= day:
                flowers_in_a_row += 1
            else:
                flowers_in_a_row = 0

            # If we have 'k' consecutive bloomed flowers, make a bouquet
            if flowers_in_a_row == k:
                flowers_in_a_row = 0
                bouquet_count += 1

        # Return True if we can make at least 'm' bouquets
        return bouquet_count >= m

    def minDays(self, bloomDay, m, k):
        """
        Function to find the minimum number of days required to make 'm' bouquets.
        """
        # If the total number of flowers required is more than available, return -1
        if m * k > len(bloomDay):
            return -1

        # Set the starting day as the minimum bloom day in the array
        start = min(bloomDay)

        # Set the ending day as the maximum bloom day in the array
        end = max(bloomDay)

        # Iterate through all possible days from minimum to maximum bloom day
        for i in range(start, end + 1):
            # If making 'm' bouquets is possible on day 'i', return 'i'
            if self.days_possible(bloomDay, i, k, m):
                return i

        # If no valid day is found, return -1
        return -1

4. Javascript Try on Compiler 
/**
 * @param {number[]} bloomDay
 * @param {number} m
 * @param {number} k
 * @return {number}
 */

var daysPossible = function (bloomDay, day, k, m) {
    let bouquetCount = 0;
    let flowersInARow = 0;

    // Iterate through each flower's bloom day
    for (let bday of bloomDay) {
        
        // Check if the flower blooms on or before the given day
        if (bday <= day)
            flowersInARow++;
        else
            flowersInARow = 0;

        // If we have 'k' consecutive bloomed flowers, make a bouquet
        if (flowersInARow === k) {
            flowersInARow = 0;
            bouquetCount++;
        }
    }

    // Return true if we can make at least 'm' bouquets
    return bouquetCount >= m;
};

var minDays = function (bloomDay, m, k) {
    let mindays = -1;

    // Set the starting day as the minimum bloom day in the array
    let start = Math.min(...bloomDay);

    // Set the ending day as the maximum bloom day in the array
    let end = Math.max(...bloomDay);

    // Iterate through all possible days from minimum to maximum bloom day
    for (let i = start; i <= end; i++) {

        // If making 'm' bouquets is possible on day 'i', return 'i'
        if (daysPossible(bloomDay, i, k, m)) {
            return i;
        }
    }

    // If no valid day is found, return -1
    return mindays;
};

Time Complexity: O(N * M)

We iterate over all possible days from min(bloomDay) to max(bloomDay) and check for each day whether we can form m bouquets using the daysPossible function.

1. daysPossible Function Complexity
The daysPossible function iterates through the bloomDay array once to count valid bouquets.
Let N be the number of flowers in bloomDay.
The function runs in O(N) time.

2. minDays Function Complexity
The function iterates over all possible days from min(bloomDay) to max(bloomDay).
Let M be the range of days, i.e., max(bloomDay) - min(bloomDay).
This results in O(M) iterations.
Each iteration calls daysPossible, which takes O(N) time.

Final Complexity : Since O(N) operations are performed for each of the O(M) days, the total complexity is: O(N * M)

where:
N = Number of flowers in bloomDay (length of the array).
M = Range of possible days, which is max(bloomDay) - min(bloomDay).

Space Complexity: O(N)

  1. Auxiliary Space Complexity: O(1)
    The algorithm only uses a few integer variables (mindays, start, end, bouquetCount, flowersInARow, etc.). These are just primitive variables that occupy O(1) space.
    Therefore, the auxiliary space complexity is O(1).
  2. Total Space Complexity: O(N)
    Since we do not create any new data structures apart from the input bloomDay, the total space complexity is O(N), where N is the size of the input array.
    Therefore, the total space complexity is O(N).

Will Brute Force Work Against the Given Constraints? 

For the current solution, the time complexity is O(N * M), where N is the number of flowers (with an upper limit of 10⁵) and M is the range of possible days, which is max(bloomDay) - min(bloomDay). In the worst-case scenario, M can be as large as 10⁹ (if the bloom days range from 1 to 10⁹), which leads to a time complexity of O(N * (max(bloomDay) - min(bloomDay))).

This can become inefficient because the difference between max(bloomDay) and min(bloomDay) can be very large, making the solution impractical for many inputs, particularly when max(bloomDay) - min(bloomDay) is close to its upper bound.

Given the constraints, with N up to 10⁵ and M reaching up to 10⁶, the solution may not execute efficiently for a wide range of inputs, especially when the range of days (max(bloomDay) - min(bloomDay)) is large. While it may work well for inputs with a smaller day range, this time complexity does not guarantee that it will perform optimally for all cases.

In competitive programming environments, problems generally allow up to 10⁶ operations per test case. For most typical inputs, the solution might work fine, but in the worst-case scenario, the time complexity could exceed the limits. Optimizations are necessary to handle inputs where the day range is large, making the solution more efficient and suitable for all possible cases.

How to optimize it?

In the previous approach, we looked at the minimum and maximum days in which flowers bloom and checked every day in that range to find the smallest day that could allow us to make m bouquets, each using k consecutive flowers. This gave us O(N * (maxDay - minDay)) time complexity, which was too slow and caused TLE (Time Limit Exceeded).

Now, let’s think about improving this.
The main issue was that we checked every day from the minimum bloom day to the maximum bloom day, which took a lot of time.

Can we make this part faster?

Yes! Here’s the hint:

We are searching for the minimum day that works, and we know it lies between the minimum bloom day and the maximum bloom day.

Now that we know the two endpoints, the minimum bloom day and the maximum bloom day, let's make a few observations:

  • The data structure is sorted:
    The range of days, from the minimum to the maximum, is naturally sorted.
  • The search space is monotonic:
    • If a certain day allows us to make m bouquets, then any day later will also work.
    • If a certain day does not allow us to make m bouquets, then any day earlier will also fail.
    • For the example with the bloom days [1, 10, 3, 10, 2] and m = 3, k = 1, the algorithm will fail to make 3 bouquets on days 1, 2, and 3 (F, F, F). Starting from day 4, it will succeed in making the bouquets (T, T, T), and the search will find that day 3 is the minimum day where this happens.
      This illustrates the monotonic property: once a day works, it will continue to work for all later days.
  • The middle element helps minimize or maximize the search space:
    If we take the middle value of the current range and check if it works (i.e., can we make at least m bouquets with k consecutive flowers on that day), we can narrow the search space:
    If it works, we move to the left half to find a smaller valid day.
    If it doesn’t work, we move to the right half to find a larger valid day.

If we plot a graph with the range of days on the x-axis and whether we can make m bouquets with k adjacent flowers on the y-axis, we can observe the following:

  • For a given day, we can either make m bouquets or not.
  • Before the minimum day (denoted as mindays), we cannot make m bouquets. This is because, for any day from the start up to mindays - 1, the required conditions for making m bouquets are not met.
  • From mindays onwards, we are able to make m or more bouquets. This is because once we reach mindays, the bloom conditions are such that we can start forming the required number of bouquets, and this condition remains valid as we go further towards the maximum day.

Thus, mindays represents the earliest day at which it becomes possible to make m bouquets, and from that point forward, making m bouquets remains feasible.

Minimum Number of Days to Make m Bouquets-graph

With these points in mind, it's clear that instead of linearly checking all values from the minimum to the maximum day, we can take the middle value and continually reduce the search space.

Does this approach remind you of something you've seen before?

Yes, we are applying binary search here. By leveraging the sorted and monotonic properties of the day range, we efficiently narrow down the search space to find the minimum day that meets the condition, instead of checking each day linearly.

💡
Check how binary search works?

Binary search can help us quickly find the minimum day that allows us to make all bouquets.

We can simply use binary search to determine the minimum day needed to make m bouquets with k consecutive flowers.

Start by taking the middle value between low (minimum bloom day) and high (maximum bloom day). If this mid-day satisfies the condition that we can make m bouquets with k consecutive flowers on that day, we store it as a potential answer and narrow the search space to the left half, looking for a smaller valid day. Otherwise, we move the search to the right half to find a larger valid day. We continue this process as long as low <= high.

Once the condition breaks, the stored answer is returned as the minimum day.

By using binary search, we can cut the search space in half at each step, which makes the solution much faster and avoids the TLE issue.

Let us understand this with a video,

0:00
/1:24

Minimum Number of Days to Make m Bouquets-optimal approach animation explaination

💡
Try it Yourself!

Let's understand with an example:

Input: bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3

  1. Initial Setup:
    start = 7 (min bloom day)
    end = 12 (max bloom day)
    We want to find the minimum day to make 2 bouquets with 3 consecutive flowers.
  2. Binary Search (Midpoint calculation in each iteration):
    Iteration 1: mid = (7 + 12) / 2 = 9
    Check if we can make 2 bouquets by day 9:
    Flowers blooming by day 9: [x, x, x, x, _, x, x]
    We can make 1 bouquet (first 3 flowers).
    Total bouquets: 1 (not enough, as we need 2).
    Since 1 bouquet is less than m = 2, move to the right half. Now, start = 10.
    Iteration 2: mid = (10 + 12) / 2 = 11
    Check if we can make 2 bouquets by day 11:
    Flowers blooming by day 11: [x, x, x, x, _, x, x]
    We can make 1 bouquet (first 3 flowers).
    Total bouquets: 1 (not enough, as we need 2).
    Since 1 bouquet is less than m = 2, move to the right half. Now, start = 12.
    Iteration 3: mid = (12 + 12) / 2 = 12
    Check if we can make 2 bouquets by day 12:
    Flowers blooming by day 10: [x, x, x, x, x, x, x]
    We can make 2 bouquet.
    Total bouquets: 2 (satisfies).
    Since we can make m bouquets, we store this as a potential answer and move to the left half to find a smaller possible answer. Now, end = 11.
    Exit Condition:
    start = 12, end = 11. since start > end, so break the loop.

Thus, the answer is 12.

How to code it up:

Here are concise steps to code up the solution generically:

Define the Binary Search Range:
Initialize low as the minimum bloom day in the bloomDay array.
Initialize high as the maximum bloom day in the bloomDay array.

Helper Function for Validation (daysPossible):
Write a function to check if it's possible to form m bouquets by a given day:
Track the number of consecutive flowers bloomed.
Track the total number of bouquets formed.
If k consecutive flowers bloom, increment the bouquet count and reset the counter.
If the bouquet count is greater than or equal to m, return true; otherwise, return false.

Binary Search Logic:
Perform binary search between low and high (bloom days range).
Calculate the middle day, mid.
Use the daysPossible function to check if it's possible to form m bouquets by mid day.
If daysPossible(mid) returns true:
Update mindays to mid (potential solution found).
Narrow the search range to the left half (high = mid - 1).
Otherwise, search the right half (low = mid + 1).

Return the Result:
Once the binary search completes, return the mindays value as the result, which represents the minimum days required to make m bouquets. If no valid solution exists, it will remain -1.

Code Implementation
1. C++ Try on Compiler 
class Solution {
    // Function to check if it's possible to make 'm' bouquets by a given 'day'
    bool daysPossible(vector<int>& bloomDay, int day, int k, int m)
    {   
        // Initialize the number of bouquets formed
        int bouquetCount = 0;
        
        // Initialize the count of consecutive bloomed flowers
        int flowersInARow = 0;

        // Iterate through each flower's bloom day
        for(auto &bday: bloomDay)
        {
            // Check if the flower blooms on or before the given day
            if(bday <= day)

                // Increment if flower blooms before or on the current day
                flowersInARow++; 
            else

                // Reset if flower hasn't bloomed yet
                flowersInARow = 0; 

            // If we have 'k' consecutive bloomed flowers, make a bouquet
            if(flowersInARow == k)
            {
                // Reset after forming a bouquet
                flowersInARow = 0; 

                // Increment bouquet count
                bouquetCount++; 
            }
        }

        // Return true if we can make at least 'm' bouquets
        return bouquetCount >= m;
    }

public:
    // Function to find the minimum number of days required
    int minDays(vector<int>& bloomDay, int m, int k) {
        
        // Initialize the result with -1 in case there's no solution
        int mindays = -1;

        // Find the minimum bloom day in the array
        int start = *min_element(bloomDay.begin(), bloomDay.end());

        // Find the maximum bloom day in the array
        int end = *max_element(bloomDay.begin(), bloomDay.end());

        // Perform binary search to find the minimum number of days required
        while(start <= end)
        {
            // Calculate the middle day in the current range
            int mid = start + (end-start)/2;

            // Check if it's possible to make 'm' bouquets on day 'mid'
            if(daysPossible(bloomDay, mid, k, m))
            {
                // Store 'mid' as a potential answer
                mindays = mid;

                // Search in the left half to find a smaller valid day
                end = mid-1;
            }
            else
                // Search in the right half to find a larger valid day
                start = mid+1;
        }

        // Return the minimum days required
        return mindays;
    }
};

2. Java Try on Compiler 
class Solution {
    // Function to check if it's possible to make 'm' bouquets by a given 'day'
    public boolean daysPossible(int[] bloomDay, int day, int k, int m) {

        // Initialize the number of bouquets formed
        int bouquetCount = 0;

        // Initialize the count of consecutive bloomed flowers
        int flowersInARow = 0;

        // Iterate through each flower's bloom day
        for (int bday : bloomDay) {

            // Check if the flower blooms on or before the given day
            if (bday <= day)

                // Increment if flower blooms before or on the current day
                flowersInARow++; 
            else

                // Reset if flower hasn't bloomed yet
                flowersInARow = 0; 

            // If we have 'k' consecutive bloomed flowers, make a bouquet
            if (flowersInARow == k) {

                // Reset after forming a bouquet
                flowersInARow = 0; 

                // Increment bouquet count
                bouquetCount++; 
            }
        }

        // Return true if we can make at least 'm' bouquets
        return bouquetCount >= m;
    }

    // Function to find the minimum number of days required
    public int minDays(int[] bloomDay, int m, int k) {
        
        // Initialize the result with -1 in case there's no solution
        int mindays = -1;

        // Find the minimum bloom day in the array
        int start = Integer.MAX_VALUE;
        for (int bday : bloomDay) {
            start = Math.min(start, bday);
        }

        // Find the maximum bloom day in the array
        int end = Integer.MIN_VALUE;
        for (int bday : bloomDay) {
            end = Math.max(end, bday);
        }

        // Perform binary search to find the minimum number of days required
        while (start <= end) {

            // Calculate the middle day in the current range
            int mid = start + (end - start) / 2;

            // Check if it's possible to make 'm' bouquets on day 'mid'
            if (daysPossible(bloomDay, mid, k, m)) {

                // Store 'mid' as a potential answer
                mindays = mid;

                // Search in the left half to find a smaller valid day
                end = mid - 1;
            } else {

                // Search in the right half to find a larger valid day
                start = mid + 1;
            }
        }

        // Return the minimum days required
        return mindays;
    }
}

3. Python Try on Compiler 
class Solution:
    # Function to check if it's possible to make 'm' bouquets by a given 'day'
    def daysPossible(self, bloomDay, day, k, m):

        # Initialize the number of bouquets formed
        bouquetCount = 0

        # Initialize the count of consecutive bloomed flowers
        flowersInARow = 0

        # Iterate through each flower's bloom day
        for bday in bloomDay:

            # Check if the flower blooms on or before the given day
            if bday <= day:

                # Increment if flower blooms before or on the current day
                flowersInARow += 1  
            else:

                # Reset if flower hasn't bloomed yet
                flowersInARow = 0  

            # If we have 'k' consecutive bloomed flowers, make a bouquet
            if flowersInARow == k:

                # Reset after forming a bouquet
                flowersInARow = 0  

                # Increment bouquet count
                bouquetCount += 1  

        # Return true if we can make at least 'm' bouquets
        return bouquetCount >= m

    # Function to find the minimum number of days required
    def minDays(self, bloomDay, m, k):

        # Initialize the result with -1 in case there's no solution
        mindays = -1

        # Find the minimum bloom day in the array
        start = min(bloomDay)

        # Find the maximum bloom day in the array
        end = max(bloomDay)

        # Perform binary search to find the minimum number of days required
        while start <= end:

            # Calculate the middle day in the current range
            mid = start + (end - start) // 2

            # Check if it's possible to make 'm' bouquets on day 'mid'
            if self.daysPossible(bloomDay, mid, k, m):

                # Store 'mid' as a potential answer
                mindays = mid
                
                # Search in the left half to find a smaller valid day
                end = mid - 1
            else:
                # Search in the right half to find a larger valid day
                start = mid + 1

        # Return the minimum days required
        return mindays

4. Javascript Try on Compiler 
/**
 * @param {number[]} bloomDay
 * @param {number} m
 * @param {number} k
 * @return {number}
 */
// Function to check if it's possible to make 'm' bouquets by a given 'day'
var daysPossible = function (bloomDay, day, k, m) {

    // Initialize the number of bouquets formed
    let bouquetCount = 0;

    // Initialize the count of consecutive bloomed flowers
    let flowersInARow = 0;

    // Iterate through each flower's bloom day
    for (let bday of bloomDay) {

        // Check if the flower blooms on or before the given day
        if (bday <= day)

            // Increment if flower blooms before or on the current day
            flowersInARow++; 
        else

            // Reset if flower hasn't bloomed yet
            flowersInARow = 0; 

        // If we have 'k' consecutive bloomed flowers, make a bouquet
        if (flowersInARow === k) {

            // Reset after forming a bouquet
            flowersInARow = 0; 

            // Increment bouquet count
            bouquetCount++; 
        }
    }

    // Return true if we can make at least 'm' bouquets
    return bouquetCount >= m;
}

var minDays = function (bloomDay, m, k) {

    // Initialize the result with -1 in case there's no solution
    let mindays = -1;

    // Find the minimum bloom day in the array
    let start = Math.min(...bloomDay);

    // Find the maximum bloom day in the array
    let end = Math.max(...bloomDay);

    // Perform binary search to find the minimum number of days required
    while (start <= end) {

        // Calculate the middle day in the current range
        let mid = Math.floor(start + (end - start) / 2);

        // Check if it's possible to make 'm' bouquets on day 'mid'
        if (daysPossible(bloomDay, mid, k, m)) {

            // Store 'mid' as a potential answer
            mindays = mid;

            // Search in the left half to find a smaller valid day
            end = mid - 1;
        } else {

            // Search in the right half to find a larger valid day
            start = mid + 1;
        }
    }

    // Return the minimum days required
    return mindays;
};

Time Complexity: O(n * log(max(bloomDay) - min(bloomDay)))

Binary Search:
We perform a binary search over the range of bloom days, which lies between the minimum and maximum values of the bloomDay array.
The range of possible days is between the minimum bloom day (min(bloomDay)) and the maximum bloom day (max(bloomDay)). This gives us a range of size O(max(bloomDay) - min(bloomDay)).

Days Check (Linear Scan):
For each mid-point of the binary search, we call the daysPossible function, which checks whether we can form m bouquets on that particular day.
The daysPossible function iterates over the bloomDay array, which has n elements. Hence, the time complexity of checking whether m bouquets can be formed is O(n).

Overall Time Complexity:
In the binary search, the number of iterations is O(log(max(bloomDay) - min(bloomDay))). This is because we are halving the search space each time.
For each iteration of the binary search, we call the daysPossible function which takes O(n) time.

Thus, the overall time complexity is: O(n * log(max(bloomDay) - min(bloomDay)))

Where:
n is the number of elements in the bloomDay array.
max(bloomDay) - min(bloomDay) represents the range of the bloom days.

Space Complexity: O(n)

  1. Auxiliary Space Complexity: O(1)
    The algorithm only uses a few integer variables (e.g., mindays, start, end, bouquetCount, flowersInARow, and mid) for the binary search and the check function. These variables occupy constant space.
    Therefore, the auxiliary space complexity is O(1).
  2. Total Space Complexity: O(n)
    The input space is the array bloomDay, which has n elements.
    Thus, the total space required for the input is O(n).

Learning Tip

Now we have successfully tackled this problem, let's try these similar problems.

1. Capacity To Ship Packages Within D Days

A conveyor belt has packages that must be shipped from one port to another within D days.The ith package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within D days.

2. Sqrt(x)

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.You must not use any built-in exponent function or operator.For example, do not use pow(x, 0.5) in C++ or x ** 0.5 in Python.

💡
Showcase your skills by joining LearnYard Technologies FZ-LLC as a Technical Content Writer. Apply now and inspire the next generation of learners—fill out the form: https://forms.gle/CGDsbGkcapSfvXKM8