1482. Minimum Number of Days to Make m Bouquets

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.

Approach 01:

#include <vector>
#include <algorithm>
#include <cmath>

class Solution {
public:
    int minDays(std::vector<int>& bloom_day, int m, int k) {
        // Check if it's possible to make m bouquets with the given flowers
        if (static_cast<long long>(m) * k > bloom_day.size()) {
            return -1;
        }

        // Helper function to calculate the number of bouquets that can be made after `waiting_days`
        auto get_bouquet_count = [&bloom_day, k](int waiting_days) -> int {
            int bouquet_count = 0;  // To store the number of bouquets we can make
            int required_flowers = 0;  // To count the current contiguous flowers that have bloomed

            for (int day : bloom_day) {
                if (day <= waiting_days) {
                    required_flowers += 1;
                    // When we have enough flowers to make one bouquet
                    if (required_flowers == k) {
                        bouquet_count += 1;
                        required_flowers = 0;  // Reset the counter for the next bouquet
                    }
                } else {
                    required_flowers = 0;  // Reset the counter if the flower hasn't bloomed yet
                }
            }
            return bouquet_count;
        };

        // Set the initial bounds for binary search
        int l = *std::min_element(bloom_day.begin(), bloom_day.end());  // Minimum possible days to wait (the earliest bloom day)
        int r = *std::max_element(bloom_day.begin(), bloom_day.end());  // Maximum possible days to wait (the latest bloom day)

        // Perform binary search to find the minimum number of days
        while (l < r) {
            int mid = (l + r) / 2;  // Calculate the midpoint

            // Check if we can make at least m bouquets with mid days of waiting
            if (get_bouquet_count(mid) >= m) {
                r = mid;  // Try a smaller number of days
            } else {
                l = mid + 1;  // Try a larger number of days
            }
        }

        // After binary search, l should be the minimum number of days needed
        return get_bouquet_count(l) >= m ? l : -1;
    }
};

from typing import List

class Solution:
    def minDays(self, bloom_day: List[int], m: int, k: int) -> int:
        # Check if it's possible to make m bouquets with the given flowers
        if len(bloom_day) < m * k:
            return -1

        def get_bouquet_count(waiting_days: int) -> int:
            bouquet_count = 0  # To store the number of bouquets we can make
            required_flowers = 0  # To count the current contiguous flowers that have bloomed

            for day in bloom_day:
                if day <= waiting_days:
                    required_flowers += 1
                    # When we have enough flowers to make one bouquet
                    if required_flowers == k:
                        bouquet_count += 1
                        required_flowers = 0  # Reset the counter for the next bouquet
                else:
                    required_flowers = 0  # Reset the counter if the flower hasn't bloomed yet

            return bouquet_count

        # Set the initial bounds for binary search
        l = min(bloom_day)  # Minimum possible days to wait (the earliest bloom day)
        r = max(bloom_day)  # Maximum possible days to wait (the latest bloom day)

        # Perform binary search to find the minimum number of days
        while l < r:
            mid = (l + r) // 2  # Calculate the midpoint

            # Check if we can make at least m bouquets with mid days of waiting
            if get_bouquet_count(mid) >= m:
                r = mid  # Try a smaller number of days
            else:
                l = mid + 1  # Try a larger number of days

        # After binary search, l should be the minimum number of days needed
        return l if get_bouquet_count(l) >= m else -1

Time Complexity:

1. Initial Checks and Setup:

   • Finding the minimum and maximum element in bloom_day using min_element and max_element each takes O(n), where n is the size of bloom_day.

2. Binary Search:

   • The binary search runs in O(log⁡R) time, where RRR is the range of days between the minimum and maximum values in bloom_day.

3. Counting Bouquets:

   • For each midpoint value in the binary search, we count the number of bouquets using the get_bouquet_count function. This function iterates through the entire bloom_day array, which takes O(n)O(n)O(n) time.

Combining these, the overall time complexity is: O(n)+O(log⁡R⋅n)=O(nlog⁡R)

Space Complexity:

The space complexity is determined by the additional space used by the algorithm apart from the input data.

1. Auxiliary Space:

   • The only additional space used is for a few integer and floating-point variables.

2. Function and Data Structures:

   • The get_bouquet_count function uses a constant amount of extra space, as it only has a few integer variables.
   • No additional data structures are used that scale with the input size.

Thus, the overall space complexity is: O(1)