DEV Community

codingpineapple
codingpineapple

Posted on

LeetCode 1482. Minimum Number of Days to Make m Bouquets (javascript solution)

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
};
Enter fullscreen mode Exit fullscreen mode

Top comments (0)