# Minimum Number of Days to Make m Bouquets
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-days-to-make-m-bouquets
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [Navi](https://scaleengineer.com/companies/navi)
---
## Problem
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`.

**Example 1:**

**Input:** bloomDay = [1,10,3,10,2], m = 3, k = 1
**Output:** 3
**Explanation:** Let us see what happened in the first three days. x means flower bloomed and _ means flower did not 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.

**Example 2:**

**Input:** bloomDay = [1,10,3,10,2], m = 3, k = 2
**Output:** -1
**Explanation:** We need 3 bouquets each has 2 flowers, that means we need 6 flowers. We only have 5 flowers so it is impossible to get the needed bouquets and we return -1.

**Example 3:**

**Input:** bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
**Output:** 12
**Explanation:** We need 2 bouquets each should have 3 flowers.
Here is the garden after the 7 and 12 days:
After day 7: [x, x, x, x, _, x, x]
We can make one bouquet of the first three flowers that bloomed. We cannot make another bouquet from the last three flowers that bloomed because they are not adjacent.
After day 12: [x, x, x, x, x, x, x]
It is obvious that we can make two bouquets in different ways.

**Constraints:**

* `bloomDay.length == n`
* `1 <= n <= 105`
* `1 <= bloomDay[i] <= 109`
* `1 <= m <= 106`
* `1 <= k <= n`

# Approaches
## Brute Force Simulation
This approach involves simulating the process day by day. We can iterate through each possible day, starting from the earliest possible bloom day, and for each day, we check if we can form the required `m` bouquets. The first day on which this condition is met will be our minimum number of days.
**Time:** O(D * N), where D is the range of days (`maxDay - minDay`) and N is the length of `bloomDay`. The outer loop iterates through all possible days, and for each day, we perform a linear scan of the `bloomDay` array. Since `maxDay` can be up to 10^9, this approach is too slow. · **Space:** O(1). We only use a few variables for counting, so the space required is constant.
**Pros:** Simple to understand and implement.; Directly models the problem's conditions.
**Cons:** Extremely inefficient for large ranges of `bloomDay` values.; Not a feasible solution for the given constraints and will cause a Time Limit Exceeded error.
### Explanation
The brute-force method directly translates the problem statement into a simulation. We test every single day from the earliest bloom time to the latest. For a given day `d`, we can determine which flowers have bloomed. Then, we can scan the garden to count how many bouquets of `k` adjacent bloomed flowers can be formed. If we can form `m` or more bouquets, we've found our answer. Since we are checking days in increasing order, the first day that satisfies the condition is guaranteed to be the minimum.

```java
public class Solution {
    public int minDays(int[] bloomDay, int m, int k) {
        int n = bloomDay.length;
        if ((long) m * k > n) {
            return -1;
        }

        int minDay = Integer.MAX_VALUE;
        int maxDay = Integer.MIN_VALUE;
        for (int day : bloomDay) {
            minDay = Math.min(minDay, day);
            maxDay = Math.max(maxDay, day);
        }

        for (int day = minDay; day <= maxDay; day++) {
            if (canMakeBouquets(bloomDay, m, k, day)) {
                return day;
            }
        }

        return -1;
    }

    private boolean canMakeBouquets(int[] bloomDay, int m, int k, int currentDay) {
        int bouquets = 0;
        int flowers = 0;
        for (int i = 0; i < bloomDay.length; i++) {
            if (bloomDay[i] <= currentDay) {
                flowers++;
            } else {
                flowers = 0;
            }

            if (flowers == k) {
                bouquets++;
                flowers = 0;
            }
        }
        return bouquets >= m;
    }
}
```
This approach is straightforward but inefficient due to the potentially large range of days we have to check.
### Algorithm
- 1. First, handle the edge case: if the total number of flowers required (`m * k`) is greater than the number of flowers available (`n`), it's impossible. Return -1.
- 2. Find the minimum (`minDay`) and maximum (`maxDay`) values in the `bloomDay` array. The answer must lie within this range.
- 3. Iterate through each day `d` from `minDay` to `maxDay`.
- 4. For each day `d`, check if it's possible to make `m` bouquets.
    - a. Initialize a counter for bouquets made (`bouquets = 0`) and a counter for consecutive bloomed flowers (`adjacentFlowers = 0`).
    - b. Iterate through the `bloomDay` array.
    - c. If a flower `bloomDay[i]` has bloomed by day `d` (i.e., `bloomDay[i] <= d`), increment `adjacentFlowers`.
    - d. If `bloomDay[i] > d`, the sequence of adjacent flowers is broken, so reset `adjacentFlowers` to 0.
    - e. If `adjacentFlowers` reaches `k`, it means we can form a bouquet. Increment `bouquets` and reset `adjacentFlowers` to 0.
- 5. If after checking day `d`, the number of `bouquets` is greater than or equal to `m`, then `d` is the minimum number of days. Return `d`.
- 6. If the loop completes without finding a suitable day, it means it's impossible to make `m` bouquets. Return -1.

## Binary Search on Days
A more efficient approach leverages the monotonic nature of the problem. If we can make `m` bouquets in `d` days, we can also make them in `d+1` days. This property allows us to use binary search on the number of days to find the minimum required day. The search space for the answer is the range of days from the minimum to the maximum value in `bloomDay`.
**Time:** O(N * log(D)), where `N` is the number of flowers and `D` is the range of days (`maxDay - minDay`). The binary search performs `log(D)` iterations, and in each iteration, the `canMakeBouquets` helper function takes `O(N)` time. This is a significant improvement over the brute-force approach. · **Space:** O(1). The algorithm uses a constant amount of extra space for variables.
**Pros:** Optimal and highly efficient.; Handles large constraints effectively.
**Cons:** The logic is slightly more complex than a direct simulation, requiring an understanding of binary search on an answer space.
### Explanation
The key insight is that the feasibility of making `m` bouquets is a monotonic function of the number of days we wait. This means we can efficiently search for the "tipping point" day where it becomes possible. Instead of checking every day one by one, binary search allows us to eliminate half of the remaining search space in each step.

The helper function, `canMakeBouquets(day)`, works the same way as in the brute-force approach. It simulates the process for a *single* given day and returns `true` or `false`. The main function uses this helper to guide its search.

```java
class Solution {
    public int minDays(int[] bloomDay, int m, int k) {
        int n = bloomDay.length;
        // If the total flowers needed is more than available, it's impossible.
        // Use long for m*k to avoid overflow.
        if ((long) m * k > n) {
            return -1;
        }

        int low = Integer.MAX_VALUE;
        int high = 0;
        for (int day : bloomDay) {
            low = Math.min(low, day);
            high = Math.max(high, day);
        }

        int ans = -1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (canMakeBouquets(bloomDay, m, k, mid)) {
                ans = mid;
                high = mid - 1; // Try for an even smaller number of days
            } else {
                low = mid + 1; // Need to wait for more days
            } 
        }

        return ans;
    }

    /**
     * Checks if it's possible to make m bouquets after a given number of days.
     */
    private boolean canMakeBouquets(int[] bloomDay, int m, int k, int day) {
        int bouquets = 0;
        int flowers = 0;
        for (int i = 0; i < bloomDay.length; i++) {
            if (bloomDay[i] <= day) {
                flowers++;
            } else {
                // This flower hasn't bloomed, so the adjacent sequence is broken.
                flowers = 0;
            }

            if (flowers == k) {
                // Found enough adjacent flowers for a bouquet.
                bouquets++;
                // Reset flower count for the next bouquet.
                flowers = 0;
            }
        }
        return bouquets >= m;
    }
}
```
This solution is highly efficient and passes within the time limits.
### Algorithm
- 1. Handle the edge case: if `m * k > n`, return -1.
- 2. Define the search range for the binary search. The lower bound `low` is the minimum value in `bloomDay`, and the upper bound `high` is the maximum value.
- 3. Initialize a variable `ans = -1` to store the result.
- 4. While `low <= high`:
    - a. Calculate the middle day `mid = low + (high - low) / 2`.
    - b. Use a helper function `canMakeBouquets(mid)` to check if it's possible to make `m` bouquets if we wait `mid` days.
    - c. If `canMakeBouquets(mid)` is true, it means `mid` is a potential answer. We try to find an even smaller number of days, so we store `mid` in `ans` and shrink the search space to the left: `high = mid - 1`.
    - d. If `canMakeBouquets(mid)` is false, we need to wait longer. We shrink the search space to the right: `low = mid + 1`.
- 5. After the binary search loop terminates, `ans` will hold the minimum number of days required. Return `ans`.

# Solutions
### Java

```java
class Solution { public int minDays ( int [] bloomDay , int m , int k ) { if ( m * k > bloomDay . length ) { return - 1 ; } int min = Integer . MAX_VALUE , max = Integer . MIN_VALUE ; for ( int bd : bloomDay ) { min = Math . min ( min , bd ); max = Math . max ( max , bd ); } int left = min , right = max ; while ( left < right ) { int mid = ( left + right ) >>> 1 ; if ( check ( bloomDay , m , k , mid )) { right = mid ; } else { left = mid + 1 ; } } return left ; } private boolean check ( int [] bloomDay , int m , int k , int day ) { int cnt = 0 , cur = 0 ; for ( int bd : bloomDay ) { cur = bd <= day ? cur + 1 : 0 ; if ( cur == k ) { cnt ++; cur = 0 ; } } return cnt >= m ; } }
```

### CPP

```cpp
class Solution { public: int minDays ( vector < int >& bloomDay , int m , int k ) { if ( m * k > bloomDay . size ()) { return - 1 ; } int mi = INT_MIN , mx = INT_MAX ; for ( int & bd : bloomDay ) { mi = min ( mi , bd ); mx = max ( mx , bd ); } int left = mi , right = mx ; while ( left < right ) { int mid = left + right >> 1 ; if ( check ( bloomDay , m , k , mid )) { right = mid ; } else { left = mid + 1 ; } } return left ; } bool check ( vector < int >& bloomDay , int m , int k , int day ) { int cnt = 0 , cur = 0 ; for ( int & bd : bloomDay ) { cur = bd <= day ? cur + 1 : 0 ; if ( cur == k ) { ++ cnt ; cur = 0 ; } } return cnt >= m ; } };
```

### Python

```python
class Solution : def minDays ( self , bloomDay : List [ int ], m : int , k : int ) -> int : if m * k > len ( bloomDay ): return - 1 def check ( day : int ) -> bool : cnt = cur = 0 for bd in bloomDay : cur = cur + 1 if bd <= day else 0 if cur == k : cnt += 1 cur = 0 return cnt >= m left , right = min ( bloomDay ), max ( bloomDay ) while left < right : mid = ( left + right ) >> 1 if check ( mid ): right = mid else : left = mid + 1 return left
```