6. Minimum days to make M bouquets.md

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

🚀 6. Minimum days to make M bouquets 🧠

The problem can be found at the following link: Problem Link

💡 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)

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)

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)

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. Let’s make this learning journey more collaborative!

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

---

📍Visitor Count