Each bouquet needs k adjacent bloomed flowers. Find minimum days to make m bouquets.
Input: bloomDay=[1,10,3,10,2], m=3, k=1 → Output: 3
Input: bloomDay=[1,10,3,10,2], m=3, k=2 → Output: -1
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
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)