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 inbloomDay
). - 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 requiresk
flowers, ifm * 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 ifm
bouquets can be made by a given day, sayday
. Here's how it works:- It initializes two counters:
cnt
(the number of bouquets that can be made by the dayday
) andcur
(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 increasecur
by 1, signifying that this flower can be part of a current bouquet. - If
cur
becomes equal tok
, then we have foundk
adjacent flowers, and therefore we incrementcnt
by 1 (signifying one complete bouquet) and resetcur
to 0 to start counting for the next bouquet. - If, by the end of the array,
cnt
is greater than or equal tom
, it means we can make the required number of bouquets by the dayday
, and the function returnsTrue
. Otherwise, it returnsFalse
.
- It initializes two counters:
-
After defining the
check
function, binary search is employed to find the minimum number of days required to makem
bouquets. Here's how:- Set
left
to the minimum value inbloomDay
(the earliest possible day a flower can bloom) andright
to the maximum value inbloomDay
(the latest possible day a flower can bloom). - While
left
is less thanright
, we calculate the midpointmid
using the expression(left + right) >> 1
which is equivalent to(left + right) // 2
. - Utilize the
check
function onmid
. If it returnsTrue
, it indicates that we can potentially make the bouquets even earlier, so we setright
tomid
. Otherwise, ifcheck
returnsFalse
, it means we need more time, so we updateleft
tomid + 1
. - This process continues to narrow down the range until
left
equalsright
, which would be the minimum number of days required to make the bouquets.
- Set
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 EvaluatorExample 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 now1
. - 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 now1
(reset because the previous flower wasn't bloomed by day 8). - Flower 5 (
bloomDay[4]
): Blooms by day 8? Yes.cur
is now2
.
- Flower 1 (
- Now
cur
equalsk
, we have a complete bouquet. Socnt
is now1
andcur
resets to0
. - We have finished checking all flowers and found
cnt = 1
, which is less thanm = 2
. Therefore, we cannot make enough bouquets by day 8.
- Starting from the first flower, we loop through
- Since
check
returnedFalse
, we cannot make 2 bouquets by day 8, so we move ourleft
boundary up.left
is now9
.
Day 10 (Second Iteration):
- New midpoint:
mid = (left + right) // 2 = (9 + 12) // 2 = 10
- Function
check
withday = 10
:- Loop through
bloomDay
:- Flower 1 blooms by day 10? Yes.
cur
is1
. - Flower 2 blooms by day 10? No.
- Flower 3 blooms by day 10? Yes.
cur
is1
(reset because the previous flower wasn't bloomed by day 10). - Flower 4 blooms by day 10? Yes.
cur
is now2
(we have the second bouquet).
- Flower 1 blooms by day 10? Yes.
- We increment
cnt
to2
since we have another complete bouquet. - We can make the required number of bouquets by day 10, so
check
returnsTrue
.
- Loop through
- Since
check
returnedTrue
, we can potentially make the bouquets even earlier, so we move ourright
boundary down.right
is now10
.
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.
Is the following code DFS or BFS?
void search(Node root) { if (!root) return; visit(root); root.visited = true; for (Node node in root.adjacent) { if (!node.visited) { search(node); } } }
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!