Description:
Given an integer array bloomDay, an integer m and an integer k.
We need to make m bouquets. To make a bouquet, you need to use k adjacent flowers from the garden.
The garden consists of n flowers, the ith 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 make m bouquets from the garden. If it is impossible to make m bouquets return -1.
Solution:
Time Complexity : O(nlog(n))
Space Complexity: O(1)
// Binary Search
var minDays = function(bloomDay, m, k) {
// Check if we can make m bouquets given in day days
function checkCondition(day) {
let bouq = 0
let flowers = 0
for(const bloom of bloomDay) {
if(day >= bloom) flowers++
else flowers = 0
if(flowers===k) {
bouq++
flowers=0
}
}
// If we can make m or more bouquets, check if we can do it faster
return bouq >= m
}
// It is impossible to make m bouquets if we don't have enough flowers
if(m * k > bloomDay.length) return -1
// The fastest we can make a bouquet is the min of bloomDay and the slowest we can make a bouquet is the max of bloomDay
let left = Math.min(...bloomDay), right = Math.max(...bloomDay)
// Binary search template
while(left < right) {
const mid = left + Math.floor((right-left)/2)
if(checkCondition(mid)) {
right = mid
} else {
left = mid + 1
}
}
return left
};
Top comments (0)