Your Web News in One Place

Help Webnuz

Referal links:

Sign up for GreenGeeks web hosting
May 14, 2021 09:44 pm GMT

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 Searchvar 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};

Original Link: https://dev.to/cod3pineapple/leetcode-1482-minimum-number-of-days-to-make-m-bouquets-javascript-solution-5gfp

Share this article:    Share on Facebook
View Full Article

Dev To

An online community for sharing and discovering great ideas, having debates, and making friends

More About this Source Visit Dev To