[Leetcode problems]1482. Minimum Number of Days to Make m Bouquets

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.
 
Example 1:
Input: bloomDay = [1,10,3,10,2], m = 3, k = 1 
Output: 3 
Explanation: Let's see what happened in the first three days. x means flower bloomed and _ means flower didn't bloom in the garden. We need 3 bouquets each should contain 1 flower. After day 1: [x, _, _, _, _] // we can only make one bouquet. After day 2: [x, _, _, _, x] // we can only make two bouquets. After day 3: [x, _, x, _, x] // we can make 3 bouquets. The answer is 3.

Brute force – O(n*max(bloomDay))

The most straightforward approach is to iterate from day 1 to day max(bloomDay), and in each iteration, we would scan the array to determine how many bouquets we can get, leading to O(n*max(bloomDay)). The scanning code is as follows:

        def helper(day):
            flowers = bouq = 0
            for f in bloomDay:
                flowers = 0 if f > day else flowers + 1
                if flowers >= k:
                    flowers = 0
                    bouq += 1
                    if bouq == m:
                        break
            return bouq == m

To finish it, we add iteration code to it so we have:

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        # if m*k > len(bloomDay), it is impossible
        if m*k > len(bloomDay):
            return -1
        # helper function to determine being qualified or not
        def helper(day):
            flowers = bouq = 0
            for f in bloomDay:
                flowers = 0 if f > day else flowers + 1
                if flowers >= k:
                    flowers = 0
                    bouq += 1
                    if bouq == m:
                        break
            return bouq == m
        for i in range(1,max(bloomDay)+1):
            if helper(i):
                return i

Not surprisingly, we will get TLE.

Binary Search – O(nlog(max(bloomDay)))

To optimize it, and we notice that days actually ranging 1...n are sorted, therefore we can apply Binary Search to find the minimal number of days. While applying Binary Search, considering mid=(left+right)/2, when mid is qualified, we would let right = mid because we want to find the smallest answer, and mid may or may not be the answer; when mid is not qualified, we would let left = mid + 1 as we can assert that mid is not the answer. After simply changing iteration to Binary Search, the code is as follows:

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        # if m*k > len(bloomDay), it is impossible
        if m*k > len(bloomDay):
            return -1
        # helper function to determine being qualified or not
        def helper(day):
            flowers = bouq = 0
            for f in bloomDay:
                flowers = 0 if f > day else flowers + 1
                if flowers >= k:
                    flowers = 0
                    bouq += 1
                    if bouq == m:
                        break
            return bouq == m
        # binary search
        left, right = 1, max(bloomDay)
        while left < right:
            mid = (left+right) // 2
            if helper(mid):
                right = mid
            else:
                left = mid + 1
        return left

Reference

https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets/discuss/686316/JavaC%2B%2BPython-Binary-Search

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments