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 flowersfrom the garden. The garden consists of`n`

flowers, the`ith`

flower will bloom in the`bloomDay[i]`

and then can be used inexactly onebouquet. Returnthe minimum number of daysyou 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 = 1Output:3Explanation: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
```