---
Difficulty: Medium
Source: 160 Days of Problem Solving (BONUS PROBLEMS 🎁)
Tags:
  - Binary Search
  - Greedy
  - Arrays
---

# 🚀 _6. Minimum days to make M bouquets_ 🧠

The problem can be found at the following link: [Problem Link](https://www.geeksforgeeks.org/batch/gfg-160-problems/track/searching-bonus-problems/problem/minimum-days-to-make-m-bouquets)

## 💡 **Problem Description:**

You have a row of flowers, where each flower blooms after a specific day. The array `arr[]` represents the blooming schedule, where `arr[i]` is the day the flower at position `i` will bloom. To create a bouquet, you need to collect `k` adjacent bloomed flowers. Each flower can only be used in one bouquet.

Your goal is to find the minimum number of days required to make exactly `m` bouquets. If it is not possible to make `m` bouquets with the given arrangement, return `-1`.

## **🔍 Example Walkthrough**

**Input:**

```
m = 3, k = 2, arr[] = [3, 4, 2, 7, 13, 8, 5]
```

**Output:**

```
8
```

**Explanation:**  
We need 3 bouquets, each containing 2 flowers. After day 8: [x, x, x, x, _, x, x], we can make:

- First bouquet from flowers at indices 0 and 1,
- Second bouquet from flowers at indices 2 and 3,
- Third bouquet from flowers at indices 4 and 5.

After day 8, we can make 3 bouquets, so the answer is 8.

**Input:**

```
m = 2, k = 3, arr[] = [5, 5, 5, 5, 10, 5, 5]
```

**Output:**

```
10
```

**Explanation:**  
We need 2 bouquets, each containing 3 flowers. After day 5: [x, x, x, x, _, x, x], we can make the first bouquet from the first 3 flowers. After day 10: [x, x, x, x, x, x, x], we can form the second bouquet. So the answer is 10.

**Input:**

```
m = 3, k = 2, arr[] = [1, 10, 3, 10, 2]
```

**Output:**

```
-1
```

**Explanation:**  
To make 3 bouquets, each containing 2 flowers, we need a total of 6 flowers. However, there are only 5 flowers in the array, so it is impossible to create 3 bouquets. The answer is `-1`.

### Constraints:

- $1 ≤ k ≤ arr.size() ≤ 10^5$
- $1 ≤ m ≤ 10^5$
- $1 ≤ arr[i] ≤ 10^9$

## 🎯 **My Approach:**

### **Step-by-Step Explanation:**

1. **Initial Check:**

   - If `m * k > arr.size()`, it's impossible to form `m` bouquets because we need at least `m * k` flowers. Return `-1` immediately.

2. **Binary Search for Minimum Days:**

   - The key idea here is to use binary search on the number of days to find the minimum day in which we can form exactly `m` bouquets.
   - The search range is between the earliest blooming day (1) and the latest blooming day (the maximum value in the array).

3. **Greedy Approach for Bouquet Formation:**

   - For each day in the binary search, we simulate the process of making bouquets:
     - Traverse the array and count adjacent bloomed flowers.
     - Once we collect `k` adjacent flowers, treat them as a bouquet and reset the count.
     - If we can form `m` bouquets, continue searching in the left half of the days, else search in the right half.

4. **Termination Condition:**
   - The binary search stops when `low == high`, at which point `low` represents the minimum day on which it's possible to form exactly `m` bouquets.

## 🕒 **Time and Auxiliary Space Complexity**

- **Time Complexity:**

  - Binary search runs for `O(log(max(arr)))` iterations, where `max(arr)` is the maximum number in the array.
  - For each binary search iteration, we scan the entire array (`O(n)`), so the overall time complexity is `O(n * log(max(arr)))`.

- **Space Complexity:**
  - The space complexity is `O(n)` as we use a constant amount of extra space during the binary search and simulation process.

## 📝 **Solution Code**

## **Code (Cpp)**

```cpp
class Solution {
public:
    int minDaysBloom(int m, int k, vector<int>& arr) {
        if (m * k > arr.size()) return -1;

        int low = 1, high = *max_element(arr.begin(), arr.end());
        while (low < high) {
            int mid = low + (high - low) / 2, cnt = 0, parts = 0;
            for (int n : arr) {
                cnt = (n <= mid) ? cnt + 1 : 0;
                if (cnt == k) parts++, cnt = 0;
            }
            (parts < m) ? low = mid + 1 : high = mid;
        }
        return low;
    }
};
```

## **Code (Java)**

```java
class Solution {
    public static int minDaysBloom(int m, int k, int[] arr) {
        if (m * k > arr.length) return -1;

        int low = 1, high = Arrays.stream(arr).max().getAsInt();
        while (low < high) {
            int mid = low + (high - low) / 2;
            int cnt = 0, parts = 0;
            for (int n : arr) {
                cnt = (n <= mid) ? cnt + 1 : 0;
                if (cnt == k) {
                    parts++;
                    cnt = 0;
                }
            }
            if (parts < m) low = mid + 1;
            else high = mid;
        }
        return low;
    }
}
```

## **Code (Python)**

```python
class Solution:
    def minDaysBloom(self, m, k, arr):
        if m * k > len(arr): return -1

        low, high = 1, max(arr)
        while low < high:
            mid = (low + high) // 2
            cnt = parts = 0
            for n in arr:
                cnt = cnt + 1 if n <= mid else 0
                if cnt == k:
                    parts += 1
                    cnt = 0
            if parts < m: low = mid + 1
            else: high = mid
        return low
```

## 📢 Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: [Any Questions](https://www.linkedin.com/in/patel-hetkumar-sandipbhai-8b110525a/). Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

<div align="center">
  <h3><b>📍Visitor Count</b></h3>
</div>

<p align="center">
  <img src="https://visitor-badge.laobi.icu/badge?page_id=Hunterdii.GeeksforGeeks-POTD" />
</p>