Given bloomDay[], m bouquets, and k consecutive flowers per bouquet, return the minimum number of days to make m bouquets, or -1 if impossible.
Input: bloomDay=[1,10,3,10,2], m=3, k=1 → Output: 3Input: bloomDay=[1,10,3,10,2], m=3, k=2 → Output: -1
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.
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)