Minimum Number of Days to Make m Bouquets from Adjacent Flowers in the Garden

Every petal is a proof of the beauty of computation

The question painted a very pretty albeit annoying depiction of a garden. Here it goes:

Given an integer array bloomDay, an integer m and an integer k. We need 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.

Here’s my attempt to tackle this one:

#include <vector>
class Solution {
public:
    int minDays(vector<int>& bloomDay, int m, int k) {
        int lastDay=0;
        //calculate total number of days
        for(int i=0; i<bloomDay.size(); i++)
            if(bloomDay[i]>lastDay)
                lastDay = bloomDay[i];
int lo = 0;
        int hi = lastDay;
        int mid;
        int ctr;
        int bouq_ctr;
while(lo<=hi) {
            mid = (lo+hi)/2;
            //calculate the number of bouquets on the mid'th day
            ctr = 0;
            bouq_ctr = 0;
            for(int j=0; j<bloomDay.size(); j++) {
                if(bloomDay[j]<=mid)
                    ctr++;
                else
                    ctr = 0;
                if(ctr == k){
                    bouq_ctr++;
                    ctr = 0;
                }
            }
            //do usual binary search based on your result and lessen the number of days
            if (bouq_ctr >= m) {
                ctr = 0;
                bouq_ctr = 0;
                for(int j=0; j<bloomDay.size(); j++) {
                    if(bloomDay[j]<=mid-1)
                        ctr++;
                    else
                        ctr = 0;
                    if(ctr == k){
                        bouq_ctr++;
                        ctr = 0;
                    }
                }
                if(bouq_ctr<m)
                    return mid;
                hi = mid-1;
            }
            else
                lo = mid+1;
}
        return -1;
    }
};

Let’s try and break this down:

We start by calculating the total number of days we’re dealing with by finding the maximum of the bloomDay array.

int lastDay=0;
//calculate total number of days
for(int i=0; i<bloomDay.size(); i++)
    if(bloomDay[i]>lastDay)
        lastDay = bloomDay[i];

Now we know that we want to find a specific day when we will be able to get the required number of bouquets. So a naive approach would be to calculate the bouquets that can be collected on each day.

But before that, how do you calculate the number of bouquets on a single day?

We could go through the garden, one plant at a time; and enable a counter to check if the bloomDay of that plant is equal to or less than the day we are calculating the number of bouquets for.

If it is, we increment the counter and place a check to see if it has reached the minimum number of flowers for a full bouquet i.e. k.

If it has, we increase another counter especially for the number of bouquets.

ctr = 0;
            bouq_ctr = 0;
            for(int j=0; j<bloomDay.size(); j++)
// mid is the day we are finding the number of bouquets for
                    if(bloomDay[j]<=mid)
                    ctr++;
                else
                    ctr = 0;
                if(ctr == k){
                    bouq_ctr++;
                    ctr = 0;
                }
            }

So, the takeaway here would be that calculating the number of bouquets on a single day is itself a tedious process. Putting this inside a loop for the number of days would be even more cumbersome.

It would work, but your code judge’s test cases probably won’t wait that long. And neither should you.

So what do we do?

Think about it.

• You don’t need to calculate the number of bouquets on all the days to figure out the specific day.
• If you find the number of bouquets on a certain day, you can be sure that the following days will have that same number or more.

These couple of points gravitate towards an easier method than having a full loop-in-loop with O(n²) worst time complexity.

Binary search. Now the answer is much more simpler to code.

int lo = 0;
        int hi = lastDay;
        int mid;
        int ctr;
        int bouq_ctr;
while(lo<=hi) {
            mid = (lo+hi)/2;
            //calculate the number of bouquets on the mid'th day
            ctr = 0;
            bouq_ctr = 0;
            for(int j=0; j<bloomDay.size(); j++) {
                if(bloomDay[j]<=mid)
                    ctr++;
                else
                    ctr = 0;
                if(ctr == k){
                    bouq_ctr++;
                    ctr = 0;
                }
            }
            //do usual binary search based on your result and lessen the number of days
            if (bouq_ctr >= m) {
                ctr = 0;
                bouq_ctr = 0;
                for(int j=0; j<bloomDay.size(); j++) {
                    if(bloomDay[j]<=mid-1)
                        ctr++;
                    else
                        ctr = 0;
                    if(ctr == k){
                        bouq_ctr++;
                        ctr = 0;
                    }
                }
                if(bouq_ctr<m)
                    return mid;
                hi = mid-1;
            }
            else
                lo = mid+1;
}
        return -1;
    }
};

It looks big but really all I did was put that bouquet calculation for each day into this loop, and that is used in the condition for the binary search.

Now if you’ve gone through that piece of code, this part might throw you off from the normal way we implement binary search.

if (bouq_ctr >= m) {
                ctr = 0;
                bouq_ctr = 0;
                for(int j=0; j<bloomDay.size(); j++) {
                    if(bloomDay[j]<=mid-1)
                        ctr++;
                    else
                        ctr = 0;
                    if(ctr == k){
                        bouq_ctr++;
                        ctr = 0;
                    }
                }

Why are we calculating the number of bouquets for the previous day?

Remember, when you’re doing binary search you may get a day that has m bouquets, but that does not imply there weren’t m bouquets the day before.

So before proclaiming the answer, check whether the previous day had less than m bouquets; and only if it does, you are in the clear.

This was my interpretation and a code leaning more towards intuition and passing the test cases than optimization. Hopefully it helped you, please comment with more optimal methods.