DAY 76 - Minimum Number of days to make m bouquets.

Hey Guys!. It's day 76 and we are back with another question. It's quite similar to the last one so I will not be going through the brute force approach in this one.

Question:

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.

Intuition and Approach:

• This solution addresses the problem of finding the minimum number of days required to grow enough flowers to create a specified number of bouquets while adhering to given constraints.

Let's analyze the key components and the algorithm's approach:

• The canMakeBouquets function determines if it's possible to create the required number of bouquets on a given day. It does this by iterating through the array of flowers, tracking the flowers' count and the number of bouquets that can be made.
• The minDays function calculates the minimum number of days required to create the required number of bouquets. It first checks if the total number of required flowers exceeds the total available flowers. If this is the case, it returns -1 as it's impossible to achieve the desired number of bouquets.
• The algorithm then performs a binary search to find the optimal day to create the required bouquets. It initializes the search range based on the minimum and maximum bloom days of the flowers.
• Inside the binary search loop, the canMakeBouquets function is used to check if creating the required number of bouquets is possible on the current day. Based on the result, the search range is adjusted accordingly.

Code:

class Solution {
public:
    bool canMakeBouquets(vector<int> &flowers, int day, int requiredBouquets, int flowersPerBouquet) {
        int n = flowers.size();
        int flowersCount = 0;
        int bouquetCount = 0;

        for (int i = 0; i < n; i++) {
            if (flowers[i] <= day) {
                flowersCount++;
            } else {
                bouquetCount += (flowersCount / flowersPerBouquet);
                flowersCount = 0;
            }
        }

        bouquetCount += (flowersCount / flowersPerBouquet);
        return bouquetCount >= requiredBouquets;
    }

    int minDays(vector<int>& bloomDay, int m, int k) {
        long long totalRequiredFlowers = m * 1ll * k * 1ll;
        int n = bloomDay.size();

        if (totalRequiredFlowers > n) {
            return -1; // Impossible case
        }

        int minDay = INT_MAX, maxDay = INT_MIN;

        for (int i = 0; i < n; i++) {
            minDay = min(minDay, bloomDay[i]);
            maxDay = max(maxDay, bloomDay[i]);
        }

        int low = minDay, high = maxDay;

        while (low <= high) {
            int mid = (low + high) / 2;

            if (canMakeBouquets(bloomDay, mid, m, k)) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return low;
    }
};

Complexity Analysis: