1482. Minimum Number of Days to Make m Bouquets

Problem Description

In this problem, we have an integer array bloomDay where each element represents the day on which a particular flower will bloom. We are also given two integers m (the number of bouquets we want to create) and k (the number of adjacent flowers needed to create one bouquet). The goal is to find out the minimum number of days we need to wait until we can make exactly m bouquets using k adjacent flowers for each bouquet.

The garden is comprised of n flowers, and the i-th flower will bloom on bloomDay[i]. We can use each flower in exactly one bouquet once it has bloomed.

If it is impossible to make m bouquets with the given constraints, the function should return -1.

Example: Given bloomDay = [1, 10, 3, 10, 2], m = 3, k = 1, the output is 3 because on the third day, three flowers are bloomed which is enough to make 3 bouquets as 'k' is 1.

Intuition

The solution to this problem involves a binary search for the minimum number of days required to make m bouquets. Binary search is chosen because we are dealing with an optimization problem where we want to minimize the number of days we have to wait.

Here's the intuition for why binary search can be applied:

We know the possible range of days is between the day the earliest flower blooms (minimum value in bloomDay) and the day the last flower blooms (maximum value in bloomDay).
If we can make m bouquets on a certain day 'x', it means we can also do it on any day after 'x' (as more flowers would be bloomed).
Inversely, if we cannot make m bouquets on a certain day 'y', we will not be able to do it on any day before 'y'.

With binary search, we can efficiently narrow down the range to find the minimum number of days required. The check function inside the Solution class is used to verify if a certain number of days day is sufficient to make m bouquets by scanning through bloomDay and counting flowers bloomed. We increment the count cur for consecutive bloomed flowers and when cur equals k, we increment the number of bouquets cnt. If cnt meets or exceeds m, the function returns True; otherwise, it returns False.

The main function then uses this check function to adjust the binary search boundaries (left and right) until the minimum day is found, where left will eventually hold the minimum day required to make m bouquets.

Learn more about Binary Search patterns.

Solution Approach

The implementation of the solution makes use of a binary search algorithm and a counter pattern to verify the conditions. Below is a step-by-step walk-through of how the algorithm works:

We begin by checking if it is even possible to make m bouquets. Since each bouquet requires k flowers, if m * k is greater than the total number of flowers available (len(bloomDay)), it is impossible to make the required number of bouquets and we immediately return -1.
The check function is defined to determine if m bouquets can be made by a given day, say day. Here's how it works:
- It initializes two counters: cnt (the number of bouquets that can be made by the day day) and cur (the number of adjacent bloomed flowers we are currently considering for a bouquet).
- The function goes through each flower's bloom day in bloomDay.
- For each flower, if it is bloomed by the day day (bd <= day), we increase cur by 1, signifying that this flower can be part of a current bouquet.
- If cur becomes equal to k, then we have found k adjacent flowers, and therefore we increment cnt by 1 (signifying one complete bouquet) and reset cur to 0 to start counting for the next bouquet.
- If, by the end of the array, cnt is greater than or equal to m, it means we can make the required number of bouquets by the day day, and the function returns True. Otherwise, it returns False.
After defining the check function, binary search is employed to find the minimum number of days required to make m bouquets. Here's how:
- Set left to the minimum value in bloomDay (the earliest possible day a flower can bloom) and right to the maximum value in bloomDay (the latest possible day a flower can bloom).
- While left is less than right, we calculate the midpoint mid using the expression (left + right) >> 1 which is equivalent to (left + right) // 2.
- Utilize the check function on mid. If it returns True, it indicates that we can potentially make the bouquets even earlier, so we set right to mid. Otherwise, if check returns False, it means we need more time, so we update left to mid + 1.
- This process continues to narrow down the range until left equals right, which would be the minimum number of days required to make the bouquets.

With each iteration, we effectively halve the search space, leading to a time complexity of O(log(max(bloomDay) - min(bloomDay))) * O(n), where O(n) is the time complexity of the check function since it scans through the entire bloomDay array.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's go through an example to illustrate the solution approach with bloomDay = [7, 12, 9, 5, 4], m = 2 bouquets, and k = 2 adjacent flowers needed for each bouquet. We want to find out the minimum number of days we need to wait to make exactly 2 bouquets with 2 flowers each.

Step 1: Preliminary Check

First, we verify whether it is possible to make m bouquets from the available number of flowers. We have m * k = 2 * 2 = 4 flowers needed and there are 5 flowers in total (len(bloomDay) = 5). Since we have more flowers than needed, it's possible to proceed.

Step 2: Setting Up Binary Search

Now, we prepare for binary search. The earliest a flower can bloom is day 4, and the latest is day 12. So we set left to 4 and right to 12.

Step 3: Binary Search and the `check` Function

We will use a binary search along with the check function to narrow down the days.

Day 8 (First Iteration):

Midpoint: mid = (left + right) // 2 = (4 + 12) // 2 = 8
We use the check function to see if we can make 2 bouquets by day 8.
Function check: bloomDay = [7, 12, 9, 5, 4], day = 8
- Starting from the first flower, we loop through bloomDay:
  - Flower 1 (bloomDay[0]): Blooms by day 8? Yes. cur is now 1.
  - Flower 2 (bloomDay[1]): Blooms by day 8? No.
  - Flower 3 (bloomDay[2]): Blooms by day 8? No.
  - Flower 4 (bloomDay[3]): Blooms by day 8? Yes. cur is now 1 (reset because the previous flower wasn't bloomed by day 8).
  - Flower 5 (bloomDay[4]): Blooms by day 8? Yes. cur is now 2.
- Now cur equals k, we have a complete bouquet. So cnt is now 1 and cur resets to 0.
- We have finished checking all flowers and found cnt = 1, which is less than m = 2. Therefore, we cannot make enough bouquets by day 8.
Since check returned False, we cannot make 2 bouquets by day 8, so we move our left boundary up. left is now 9.

Day 10 (Second Iteration):

New midpoint: mid = (left + right) // 2 = (9 + 12) // 2 = 10
Function check with day = 10:
- Loop through bloomDay:
  - Flower 1 blooms by day 10? Yes. cur is 1.
  - Flower 2 blooms by day 10? No.
  - Flower 3 blooms by day 10? Yes. cur is 1 (reset because the previous flower wasn't bloomed by day 10).
  - Flower 4 blooms by day 10? Yes. cur is now 2 (we have the second bouquet).
- We increment cnt to 2 since we have another complete bouquet.
- We can make the required number of bouquets by day 10, so check returns True.
Since check returned True, we can potentially make the bouquets even earlier, so we move our right boundary down. right is now 10.

Since left is now equal to right which is 10, we have found the minimum number of days required to make m bouquets which is 10 days.

Solution Implementation

1from typing import List
2
3class Solution:
4    def min_days(self, bloom_day: List[int], m: int, k: int) -> int:
5        # If it's impossible to make m bouquets, return -1
6        if m * k > len(bloom_day):
7            return -1
8
9        # Helper function to check if it's possible to make m bouquets in 'day'
10        # by checking the array using a sliding window technique
11        def can_make_bouquets(day: int) -> bool:
12            bouquets = 0 # number of bouquets that can be made
13            flowers_in_row = 0 # number of adjacent flowers blooming in a row
14
15            # Loop through each bloom day
16            for bloom in bloom_day:
17                # If the flower bloom day is less than or equal to the chosen day, it will bloom
18                if bloom <= day:
19                    flowers_in_row += 1
20                    # If we have enough flowers in a row, we can make a bouquet
21                    if flowers_in_row == k:
22                        bouquets += 1
23                        flowers_in_row = 0 # Reset for the next potential bouquet
24                else:
25                    flowers_in_row = 0 # Reset counter if the flower won't bloom
26
27            # Check if we can make at least m bouquets
28            return bouquets >= m
29
30        # Use binary search to find the minimum day to make all m bouquets
31        # Start by setting the search space between the earliest and the latest bloom day        
32        left, right = min(bloom_day), max(bloom_day)
33      
34        # Continue searching while the search space is valid
35        while left < right:
36            # Take the mid-point of the search space
37            mid = (left + right) // 2
38            # Check if we can make the required number of bouquets by this day
39            if can_make_bouquets(mid):
40                right = mid # If yes, try to find a smaller day
41            else:
42                left = mid + 1 # If not, discard the left half of the search space
43              
44        # When the search space is reduced to a single element, it's the minimum day
45        return left
46

1class Solution {
2
3    // Determines the minimum number of days required to get m bouquets of k consecutive flowers
4    public int minDays(int[] bloomDay, int m, int k) {
5        // If there are not enough flowers to make the required bouquets, return -1
6        if (m * k > bloomDay.length) {
7            return -1;
8        }
9        // Initialize the minimum and maximum days from the bloomDay array
10        int minDays = Integer.MAX_VALUE, maxDays = Integer.MIN_VALUE;
11        for (int day : bloomDay) {
12            minDays = Math.min(minDays, day);
13            maxDays = Math.max(maxDays, day);
14        }
15        // Use binary search to find the minimum day
16        int left = minDays, right = maxDays;
17        while (left < right) {
18            int mid = (left + right) >>> 1;
19            // Check if it's possible to make the bouquets by this day
20            if (canMakeBouquets(bloomDay, m, k, mid)) {
21                right = mid;
22            } else {
23                left = mid + 1;
24            }
25        }
26        // The left boundary of binary search will be the answer
27        return left;
28    }
29
30    // Helper method to check if it's possible to make the required number of bouquets by day 'currentDay'
31    private boolean canMakeBouquets(int[] bloomDay, int numBouquets, int bouquetSize, int currentDay) {
32        int bouquetsMade = 0, flowersInBouquet = 0;
33        for (int day : bloomDay) {
34            // If the flower is bloomed by 'currentDay', include it in the current bouquet
35            if (day <= currentDay) {
36                flowersInBouquet++;
37                // If we've gathered enough flowers for a bouquet, increase the count and reset
38                if (flowersInBouquet == bouquetSize) {
39                    bouquetsMade++;
40                    flowersInBouquet = 0;
41                }
42            } else { 
43                // Flower is not bloomed, reset the count for the current bouquet
44                flowersInBouquet = 0;
45            }
46        }
47        // Check if we have made at least 'numBouquets' bouquets
48        return bouquetsMade >= numBouquets;
49    }
50}
51

1class Solution {
2public:
3    int minDays(vector<int>& bloomDay, int bouquetCount, int flowersPerBouquet) {
4        // If we cannot make the required number of bouquets, return -1
5        if (bouquetCount * flowersPerBouquet > bloomDay.size()) {
6            return -1;
7        }
8
9        // Set initial search range for binary search
10        int minDay = *min_element(bloomDay.begin(), bloomDay.end());
11        int maxDay = *max_element(bloomDay.begin(), bloomDay.end());
12      
13        int left = minDay, right = maxDay;
14        while (left < right) {
15            // Find the mid value of our search range
16            int mid = left + (right - left) / 2;
17          
18            // Check if it is possible to make the required bouquets by mid day
19            if (canMakeBouquets(bloomDay, bouquetCount, flowersPerBouquet, mid)) {
20                right = mid; // It is possible, look for a smaller day in the left half
21            } else {
22                left = mid + 1; // Not possible, look for a possible day in the right half
23            }
24        }
25
26        // At this point, left is the minimum day on which we can make the bouquets
27        return left;
28    }
29
30    // Helper function to verify if we can make the required number of bouquets by a given day
31    bool canMakeBouquets(vector<int>& bloomDay, int bouquetCount, int flowersPerBouquet, int day) {
32        int bouquetsMade = 0; // Bouquets made so far
33        int flowersCollected = 0; // Flowers in the current bouquet
34      
35        for (int bloom : bloomDay) {
36            // Collect flower if bloomed by 'day' or reset the current bouquet progress
37            flowersCollected = (bloom <= day) ? (flowersCollected + 1) : 0;
38          
39            // If we have enough flowers for a bouquet, increment the count and reset flowersCollected
40            if (flowersCollected == flowersPerBouquet) {
41                bouquetsMade++;
42                flowersCollected = 0;
43            }
44        }
45      
46        // Check if we have made at least the required number of bouquets
47        return bouquetsMade >= bouquetCount;
48    }
49};
50

1// Array of bloom days for individual flowers, number of bouquets to make, and number of flowers per bouquet
2function minDays(bloomDay: number[], bouquetCount: number, flowersPerBouquet: number): number {
3    // Cannot make the required number of bouquets with the available flowers
4    if (bouquetCount * flowersPerBouquet > bloomDay.length) {
5        return -1;
6    }
7
8    // Determine the lowest and highest bloom day to establish the binary search range
9    let minDay = Math.min(...bloomDay);
10    let maxDay = Math.max(...bloomDay);
11  
12    // Initialize binary search bounds
13    let left = minDay, right = maxDay;
14    while (left < right) {
15        // Find the midpoint in the current search range
16        let mid = left + Math.floor((right - left) / 2);
17      
18        // Check if we can make the required bouquets by this midpoint day
19        if (canMakeBouquets(bloomDay, bouquetCount, flowersPerBouquet, mid)) {
20            // Possible to make bouquets, try finding an earlier day in the left half
21            right = mid;
22        } else {
23            // Can't make bouquets, seek a later day in the right half
24            left = mid + 1;
25        }
26    }
27
28    // 'left' is the earliest day we can create the required bouquets
29    return left;
30}
31
32// Helper function checks if the required number of bouquets can be made by a specific day
33function canMakeBouquets(bloomDay: number[], bouquetCount: number, flowersPerBouquet: number, day: number): boolean {
34    let bouquetsMade = 0; // Count of bouquets successfully made
35    let flowersCollected = 0; // Count of flowers collected towards the current bouquet
36  
37    // Iterate through the array of bloom days
38    for (let bloom of bloomDay) {
39        // If flower has bloomed by the given day, add to current bouquet; otherwise, reset count
40        flowersCollected = (bloom <= day) ? (flowersCollected + 1) : 0;
41      
42        // Once enough flowers are collected for a bouquet, increment count and reset for next bouquet
43        if (flowersCollected === flowersPerBouquet) {
44            bouquetsMade++;
45            flowersCollected = 0; // Start collecting for the next bouquet
46        }
47    }
48  
49    // Return true if we can make at least the required number of bouquets
50    return bouquetsMade >= bouquetCount;
51}
52

Time and Space Complexity

The code presented implements a binary search algorithm to find the minimum day on which we can obtain m bouquets of flowers, each with k blooms.

Time Complexity

The primary operation in this algorithm is the binary search, which operates between the range of the minimum and maximum bloom day. This operation takes O(log(max(bloomDay) - min(bloomDay))). Inside each iteration of the binary search, the check function is called, which iterates over all the bloom days to determine if it's possible to make m bouquets. The iteration over bloom days in the check function has a time complexity of O(n), where n is the number of elements in bloomDay.

Therefore, the overall time complexity of the algorithm is O(n * log(max(bloomDay) - min(bloomDay))).

Space Complexity

The space complexity of this algorithm is determined primarily by the variables used for keeping track of the binary search bounds and the count variables within the check function. Since the algorithm only uses a constant amount of extra space, regardless of the input size, the space complexity is O(1).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

You are given an array of intervals where intervals[i] = [start_i, end_i] represent the start and end of the ith interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Sort the intervals by their start time, then iterate through the sorted intervals, merging any overlapping intervals.

Brute force through all interval combinations and find the answer with the least total intervals.

Iterate through the intervals in their original order, merging any overlapping intervals.

Use a priority queue to keep track of the intervals, merging any overlapping intervals.

I don’t know