# Problem Statement
You are given an integer array `bloomDay`, an integer `m` and an integer `k`.
You want 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`.
## Constraints
- `bloomDay.length == n`
- `1 <= n <= `$10^5$
- `1 <= bloomDay[i] <= `$10^9$
- `1 <= m <= `$10^6$
- `1 <= k <= n`
# Solution
Since what we're looking for is monotonic, we can solve this by [[Binary Search On Answer|binary searching on the answer]]. Our predicate function will be `canMakeBouquets` and take in `daysWaited` and return whether or not we can make `m` bouquets after waiting `daysWaited` days.
To assess if making `m` bouquets is possible, we will transform our `bloomDay` array into an array of booleans (`bloomday[i] <= daysWaited`). Then we can use [[itertools.groupby]] to get the runlength of every segment. The number of bouquets we can make for a given runlength is `floor(runLength/bouquetLength)`. Calculating this for every run of adjacent flowers, we can get the number of bouquets for a given `daysWaited`.
```python
if len(bloomDay) // k < m: return -1
def canMakeBouquets(daysWaited):
hasBloomed = [bloomTime <= daysWaited for bloomTime in bloomDay]
groups = groupby(hasBloomed)
totalBouquets = 0
for groupType, group in groups:
if not groupType : continue
group = list(group)
n = len(group)
groupBouquets = n // k
totalBouquets += groupBouquets
return totalBouquets >= m
low = 1
high = max(bloomDay)
while low < high:
mid = (low + high) // 2
if canMakeBouquets(mid):
high = mid
else:
low = mid+1
return low
```
Time Complexity: O$(n \log m)$ | Space Complexity: O$(n)$