Minimum Number of Days to Make m Bouquets

Share

Given bloomDay[], m bouquets, and k consecutive flowers per bouquet, return the minimum number of days to make m bouquets, or -1 if impossible.

Example 1
Input: bloomDay=[1,10,3,10,2], m=3, k=1 → Output: 3
Example 2
Input: bloomDay=[1,10,3,10,2], m=3, k=2 → Output: -1

Solution Approach

Binary search on the day. For a given day d, count bouquets: scan bloomDay and count consecutive flowers that have bloomed by day d.

  • If m*k > n, return -1 (impossible).
  • lo=1, hi=max(bloomDay).
  • For mid day: count consecutive bloomed flowers, accumulate bouquets.
  • If bouquets >= m: hi=mid. Else lo=mid+1.
Java
class Solution {
    public int minDays(int[] bloomDay, int m, int k) {
        long need = (long) m * k;
        if (need > bloomDay.length) return -1;
        int lo = 1, hi = 0;
        for (int d : bloomDay) hi = Math.max(hi, d);
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (canMake(bloomDay, m, k, mid)) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
    private boolean canMake(int[] bloomDay, int m, int k, int day) {
        int bouquets = 0, consecutive = 0;
        for (int d : bloomDay) {
            if (d <= day) { if (++consecutive == k) { bouquets++; consecutive = 0; } }
            else consecutive = 0;
        }
        return bouquets >= m;
    }
}
  • Time Complexity: O(N log M) where M=max(bloomDay)
  • Space Complexity: O(1)