Table of contents
Problem Statement
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 kadjacent flowers from the garden.
The garden consists of n flowers, the i<sup>th</sup> 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 makembouquets from the garden. If it is impossible to make m bouquets return -1. (link)
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 == n1 <= n <= 10^51 <= bloomDay[i] <= 10^91 <= m <= 10^61 <= k <= n
Solution
Brute force Approach
We aim to create 'm' bouquets using 'k' flowers. The array bloomDay indicates the number of days after which each flower blooms, with the ith flower blooming on bloomDay[i].
If the number of flowers is fewer than what is required to make 'm' bouquets (i.e., n < m * k), then it's impossible to create 'm' bouquets.
Assuming there are enough flowers to make 'm' bouquets, we can efficiently create them by using the maximum number of days present in the array. This is because all the flowers will have bloomed, allowing us to easily pick 'k' adjacent flowers to complete the bouquets.
Therefore, we iteratively decrease the day count from the maximum day until we reach a day where it's no longer possible to create 'm' bouquets using 'k' adjacent flowers.
m = 2 and k = 3
bloomDay = [7, 7, 7, 7, 13, 11, 12, 7]
On 13th day [(Y, Y, Y), (Y, Y, Y), Y, Y]
Y- Means yes the floor got bloomed.
The grouped Y's are the adjacent flowers we take to make 1 bouqet
2 bouqets possible
bloomDay = [7, 7, 7, 7, 13, 11, 12, 7]
On 12th day [(Y, Y, Y), Y, N, (Y, Y, Y)]
2 bouqets possible
bloomDay = [7, 7, 7, 7, 13, 11, 12, 7]
On 11th day [(Y, Y, Y), Y, N, N, N, Y]
only 1 bouqet possible
Hence least possible answer is 12 days.
The primary objective is to determine, for a given time period or number of days 'd', how many bouquets can be created using 'k' adjacent flowers. For example, if there are 7 continuous adjacent flowers bloomed and k=3, then a total of 2 bouquets can be made from them. To calculate the total number of adjacent groups, we utilize a counter. We increment the counter when we encounter a bloomDay less than or equal 'd'; otherwise, we reset it to 0. Before resetting the counter to 0, we determine the number of bouquets that can be made with the current count. At the end of the iteration, we count the number of bouquets that can be made with any leftover count.
Answer range: it falls between the minimum and maximum bloom days present in the bloom array. The maximum number of bloom days present in the array provides a definite answer, as all flowers will have bloomed by this day.
class Solution {
public boolean isPossible(int[] bloomDay, int day, int m, int k){
int count = 0;
int noOfBouquets = 0;
for(int i=0; i<bloomDay.length; i++){
if(bloomDay[i]<=day){
count+=1;
}
else{
noOfBouquets += (count/k);
count = 0;
}
}
//The count can still have value
noOfBouquets+= (count/k);
return noOfBouquets>=m;
}
public int minDays(int[] bloomDay, int m, int k) {
int total = m*k;
if(total>bloomDay.length) return -1;
int max = Arrays.stream(bloomDay).max().getAsInt();
int min = Arrays.stream(bloomDay).min().getAsInt();
for(int i=min; i<=max; i++){
if(isPossible(bloomDay,i,m,k)){
return i;
}
}
return -1;
}
}
Optimal Approach
First, examine the brute force approach, then transition to applying the standard binary search method. Eventually, the 'low' pointer will indicate the minimum possible answer, while the 'high' pointer will point to an invalid one. Alternatively, you may store all potential answers in a variable and return them.
class Solution {
public boolean isPossible(int[] bloomDay, int day, int m, int k){
int count = 0;
int noOfBouquets = 0;
for(int i=0; i<bloomDay.length; i++){
if(bloomDay[i]<=day){
count+=1;
}
else{
noOfBouquets += (count/k);
count = 0;
}
}
noOfBouquets+= (count/k);
return noOfBouquets>=m;
}
public int minDays(int[] bloomDay, int m, int k) {
if(m>(bloomDay.length/k)) return -1;
// if(m*k>bloomDay.length) return -1;
int max = Arrays.stream(bloomDay).max().getAsInt();
int min = Arrays.stream(bloomDay).min().getAsInt();
int low = min;
int high = max;
while(low<=high){
int mid = (low+high)/2;
if(!isPossible(bloomDay, mid, m, k)){
low = mid +1;
}
else{
high = mid -1;
}
}
return low;
}
}