Last Updated: 4 Sep, 2021
Rose Garden
Moderate
Asked in companies
You are given 'n' roses and you are also given an array 'arr' where 'arr[i]' denotes that the 'ith' rose will bloom on the 'arr[i]th' day.
You can only pick already bloomed roses that are adjacent to make a bouquet. You are also told that you require exactly 'k' adjacent bloomed roses to make a single bouquet.
Find the minimum number of days required to make at least 'm' bouquets each containing 'k' roses. Return -1 if it is not possible.
Example :
Input: n = 9, arr = [ 1, 2, 1, 2, 7, 2, 2, 3, 1 ], k = 3, m = 2
Output: 3.
Explanation: This is because on the 3rd day: all the roses with 'arr[i]' less than equal to 3 have already bloomed, this means every rose except the 5th rose has bloomed. Now we can form the first bouquet from the first three roses and the second bouquet from the last three roses.
Input Format :
The first line contains a single integer ‘n’ denoting the roses.
The second line contains the n integers ‘arr[i]’ denoting the number of days required by the ith rose to bloom.
The third line contains two integers ‘k’ and ‘m’ denoting the number on the number of roses in a bouquet and the number of bouquets required respectively.
Output Format :
Print a single integer denoting the minimum number of days required.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function.
Approaches
Greedily try finding if it's possible to make ‘m’ bouquets after one day, you can easily do this by greedily selecting the subarray of size equal to ‘k’ as a single bouquet, so we just need to find ‘m’ of these subarrays for the answer to be equal to 1. Continue the search for the next day if you are not able to find ‘m’ subarrays each having ‘k’ bloomed roses. Finally, return the answer if you are able to find such a day.
The border case here exists when k * m > n, in this case, we won't have enough roses to make bouquets even after infinite days, so handle this case separately to avoid an infinite loop.
The steps are as follows :
- Check for the border case, if k * m > n is true then return -1.
- Initialize variable “days” equal to 1 and run a while loop for variable “days”.
- Greedily start finding subarrays of size equal to ‘k’ such that all the elements in the subarray have a value less than or equal to the current value of “days”.
- If you have found ‘m’ such subarrays then simply return the current value of “days” as the final answer.
We can clearly see that if it is possible to make ‘m’ bouquets of ‘r’ adjacent bloomed flowers in ‘d’ days, then it is also possible to do it in ‘d+1’ days. What does this mean?
We can easily apply binary search over the number of days required, if for the current value of “days” we are able to form ‘m’ bouquets, then we are sure that a more optimal answer can only exist for smaller values of “days”.
The border case here exists when k * m > n, in this case, we won't have enough roses to make bouquets even after infinite days, though the binary search approach will automatically handle this border case as we will have an upper limit on days while implementing binary search, in practice, it’s best to handle this case separately for a lesser runtime.
The steps are as follows :
- Check for the border case, if k * m > n is true then return -1.
- Initialize variable “low” equal to 0, “high” equal to 200 denoting our initial search space and also initialize “days” to store the optimal result while implementing binary search.
- Run a while loop till the condition low <= high is true.
- Inside the while loop, calculate “mid” equal to (low + high ) / 2.
- Greedily start finding subarrays of size equal to ‘K’ such that all the elements in the subarray have a value less than or equal to “mid”, if you are able to find ‘m’ such subarrays then store the value of “mid” in “days” and reduce the current search space to left half by setting “high” equal to mid-1 (we are now trying to find a lower possible answer).
- If you are not able to find ‘m’ subarrays for the current value of “mid” then reduce the search space to the right half by setting “low” equal to mid+1
- Finally, return the value of “days”.
Similar problems