Minimum Number of Days to Make m Bouquets

Share

Each bouquet needs k adjacent bloomed flowers. Find minimum days to make m bouquets.

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 answer (days). For each candidate day, count how many bouquets can be made.

  • Binary search on days [1, max(bloomDay)]
  • For given day d: count bouquets (consecutive bloomed >= k)
  • If count >= m: day d is feasible, try smaller
  • Return minimum feasible day or -1
Java
public int minDays(int[] bloomDay, int m, int k) {
    if ((long)m * k > bloomDay.length) return -1;
    int lo = 1, hi = Arrays.stream(bloomDay).max().getAsInt();
    while (lo < hi) {
        int mid = (lo + hi) / 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) { consecutive++; if (consecutive == k) { bouquets++; consecutive = 0; } }
        else consecutive = 0;
    }
    return bouquets >= m;
}
  • Time Complexity: O(n log(max))
  • Space Complexity: O(1)