1482. Minimum Number of Days to Make m Bouquets Solution | Leetcode | Binary Search

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.

class Solution {
public:
    bool isPossible(vector<int>&bloomDay,int days, int m, int k){
        int cnt = 0,res = 0;
        for(int i = 0; i<bloomDay.size(); i++){
            if(bloomDay[i]<=days)cnt++;
            else cnt = 0;
            if(cnt>=k){
                cnt = 0;
                res++;
            }
        }
        return res>=m;
    }

    int minDays(vector<int>& bloomDay, int m, int k) {
        int low = 0, mid, high = 1e9;
        while(high>=low){
            mid = low+(high-low)/2;
            if(isPossible(bloomDay,mid,m,k)){
                high = mid-1;
            } else low = mid+1;
        }
        return low > 1e9 ? -1 : low;
    }
};

Let’s analyze the main parts of the solution:

isPossible Function: Checks if we can form at least m bouquets by day days. It iterates through bloomDay and counts consecutive bloomed flowers:
```
if (bloomDay[i] <= days) cnt++;
else cnt = 0;
if (cnt >= k) {
    cnt = 0;
    res++;
}
```
Here, res counts how many bouquets we can make.

Binary Search:

low = 0
high = 1e9
while (low ≤ high):
    mid = (low + high) / 2
    if isPossible(mid):
        high = mid - 1
    else:
        low = mid + 1

This ensures we find the smallest possible day that allows making all m bouquets.

Edge Case: If the total number of flowers n is less than m × k, it’s impossible to make the required bouquets return -1.

Example walkthrough:

For bloomDay = [1,10,3,10,2], m = 3, k = 1:

Binary search range: [0, 10].
At day = 3, bloomed flowers = [x, _, x, _, x] → 3 bouquets.
Thus, the minimum number of days = 3.

This approach runs in O(n log(max(bloomDay))) efficient for large input sizes.

Tagsleetcode1482. Minimum Number of Days to Make m Bouquets

Raunit Verma

Technical Writer at CodingKaro

Share this on

1482. Minimum Number of Days to Make m Bouquets Solution | Leetcode | Binary Search

Example walkthrough:

Raunit Verma

CodingKaro App