Rose Garden

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
206 upvotes
Asked in companies
CohesityGoogle incJosh Technology Group

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1 :
9
1 2 1 2 7 2 2 3 1
3 2
Sample Output 1 :
3
Explanation For Sample Input 1 :
We will return 3, because:
All the roses with 'arr[i]' less than equal to 3 have already bloomed after 3 days, 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.
Sample Input 2 :
4
1 1 1 1
1 1
Sample Output 2 :
1
Constraints :
1 <= n <= 10^5
1 <= arr[i] <= 10^9
1 <= k <= n
1 <= m <= 10^6

Time limit: 1 sec
Hint

Constraints are small, greedily find the minimum number of days required.

Approaches (2)
Greedy

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.
Time Complexity

O( n* d ), where n denotes the number of roses and d denotes the maximum value of the array.


In the worst case we might have to include all the ‘N’ roses to make the bouquet, in this case we will need to iterate one by one till the time last rose is not bloomed, this means in the worst case we will need to run the while loop equal to the maximum array value. Also each time inside the while loop we are iterating each of the ‘N’ roses.

Hence the time complexity is O( n * d ).

Space Complexity

O( 1 )


Extra space is not used. Hence the space complexity is O( 1 ).

Code Solution
(100% EXP penalty)
Rose Garden
Full screen
Console