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.

&nbsp;
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.


&nbsp;
Constraints:


	bloomDay.length == n
	1 &lt;= n &lt;= 105
	1 &lt;= bloomDay[i] &lt;= 109
	1 &lt;= m &lt;= 106
	1 &lt;= k &lt;= n


class Solution:
    
    def minDays(self, listOfFlowerBloomDays: List[int], targetNumberOfBouquets: int, flowersPerBouquet: int) -> int:
        
        def numberOfBouquetsWeCanMakeOnThisDay(dayThatWeAreChecking):
            
            currentListOfAdjacentBloomedFlowers = []
            numberOfBouquetsWeCanMakeOnThisDay = 0
            
            for dayThatFlowerBlooms in listOfFlowerBloomDays:
                
                # check if the flower has bloomed on this day 
                if dayThatFlowerBlooms <= dayThatWeAreChecking:
                    
                    # add to the list an adjacent bloomed flowers, I use 'x' because the description uses an 'x'
                    currentListOfAdjacentBloomedFlowers.append('x')
                    
                else:
                    # we've hit a day where we don't have a bloomed flower, so the list of adjacent bloomed flowers has to be reset
                    # BUT FIRST figure out how many bouquets we can make with this list of adjacent bloomed flowers
                    numberOfBouquetsWeCanMakeOnThisDay += len(currentListOfAdjacentBloomedFlowers)//flowersPerBouquet
                    
                    # RESET list of adjacent bloomed flowers cause we're on a day where the a flower has not bloomed yet
                    currentListOfAdjacentBloomedFlowers = []
            
            # we've gone through the entire listOfFlowerBloomDays list and need to check if the "residual" current list 
            # of adjacent bloomed flowers can make a bouquet ... so handle it here
            numberOfBouquetsWeCanMakeOnThisDay += len(currentListOfAdjacentBloomedFlowers)//flowersPerBouquet
                    
            return numberOfBouquetsWeCanMakeOnThisDay
        
        
        # if the TOTAL amount of flowers we need doesn't match the number of possible flowers we can grow,
        # then the given inputs are impossible for making enough bouquets (we don't have enough flowers)
        totalNumberOfFlowersNeeded = targetNumberOfBouquets*flowersPerBouquet
        numberOfFlowersWeCanGrow = len(listOfFlowerBloomDays)
        if numberOfFlowersWeCanGrow < totalNumberOfFlowersNeeded: 
            return -1
        
        # no need to go past the day of the flower with the longest bloom date
        leftDay = 0
        rightDay = max(listOfFlowerBloomDays)
        
        while leftDay < rightDay:
            
            # currentDay is functioning as the "mid" of a binary search
            currentDay = leftDay + (rightDay-leftDay)//2
            
            # as in most binary searches, we check if the mid (which I'm calling 'currentDay') satisfies the constraint
            # that is, if we can make the target amount of bouquets on this day
            if numberOfBouquetsWeCanMakeOnThisDay(currentDay) < targetNumberOfBouquets:
                
                # womp womp, we can't make enough bouquets on this day, so set up for next iteration
                # the "correct day" is on the right side, so we get rid of all the "incorrect days" on the left side
                # by updating the left to the currentDay+1
                leftDay = currentDay+1
            else:
                
                # yay, we can make enough bouquets on this day, but we don't know if this is the "minimum day"
                # we discard the right side to keep searching
                rightDay = currentDay
        
        # leftDay >= rightDay, so we've found the "minimum day"
        return leftDay
		
class Solution {
    public int minDays(int[] bloomDay, int m, int k) {
        if(m*k > bloomDay.length) return -1;
        
        int low = Integer.MAX_VALUE, high = 0;
        for(int i:bloomDay){
            low = Math.min(low,i);
            high = Math.max(high,i);
        }
        while(low<=high){
            int mid = low + (high-low)/2;
            if(isPossible(bloomDay,mid,m,k)) high = mid - 1;
            else low = mid + 1;
        }
        return low;
    }
    private boolean isPossible(int[] bloomDay,int maxDays,int m,int k){
        for(int i=0;i<bloomDay.length;i++){
            int count = k;
            while(i<bloomDay.length && bloomDay[i]<=maxDays){
                count--;
                if(count==0){
                    m--;
                    break;
                }
                i++;
            }
            if(m==0) return true;
        }
        return false;
    }
}
class Solution {
public:
      bool check(int mid,vector<int> &v, int m, int k)
      {
          int n=v.size();
          int cnt=0;// taking cnt for the no of k adjacent bouquets possible
          for(int i=0;i<v.size();i++)
          {
              if(v[i]<=mid)
              {
                  int c=0;
                  while(i<n and v[i]<=mid)
                  {
                      i++;
                      c++;// c->checking for adjacent count
                  }
                 cnt+=c/k;
              }
          }
          if(cnt>=m)
              return true;
          return false;

      }
    int minDays(vector<int>& bloomDay, int m, int k) {
        int s=*min_element(bloomDay.begin(),bloomDay.end());
        int e=*max_element(bloomDay.begin(),bloomDay.end());
        int ans=e;
        if((m*k)>bloomDay.size())
            return -1;
        while(s<=e)
        {
           int mid=s+(e-s)/2;
            if(check(mid,bloomDay,m,k))
            {
                ans=mid;
                e=mid-1;
            }
            else
                s=mid+1;
        }
        return ans;
    }
};
var minDays = function(bloomDay, m, k) {
    if (m * k > bloomDay.length) {
        return -1;
    }

    let left = 0;
    let right = 0;

    for (const day of bloomDay) {
        left = Math.min(day, left);
        right = Math.max(day, right);
    }

    let ans = right;

    while (left < right) {
        const day = Math.floor((left + right) / 2);

        let count = 0;
        let current = 0;

        for (let j = 0; j < bloomDay.length; j++) {
            if (bloomDay[j] <= day) {
                current++;
            } else {
                current = 0;
            }

            if (current === k) {
                count++;
                current = 0;
            }
        }

        if (count === m) {
            ans = Math.min(ans, day);
        }

        if (count < m) {
            left = day + 1;
        } else {
            right = day;
        }
    }

    return ans;
};
Minimum Number of Days to Make m Bouquets