Minimum Number of Days to Make m Bouquets
Problem
Flower i blooms on day bloomDay[i]. A bouquet needs k adjacent bloomed flowers, and each flower can be used once. Return the minimum day by which you can make m bouquets, or −1 if it is 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
That needs 6 flowers, but there are only 5.
Test cases
Case 1
Input: [1,10,3,10,2], 3, 1 Expected: 3
Case 2
Input: [1,10,3,10,2], 3, 2 Expected: -1
Case 3
Input: [7,7,7,7,12,7,7], 2, 3 Expected: 12
View solutionHide solution1 approach
1. Binary search on the day
Time O(n log max)Space O(1)
By day d every flower with bloomDay ≤ d is open; count runs of k adjacent open flowers. More days never means fewer bouquets.
function minDays(bloomDay, m, k) { if (m * k > bloomDay.length) return -1; const canMake = (day) => { let bouquets = 0, run = 0; for (const b of bloomDay) { run = b <= day ? run + 1 : 0; if (run === k) { bouquets++; run = 0; } } return bouquets >= m; }; let lo = Math.min(...bloomDay), hi = Math.max(...bloomDay); while (lo < hi) { const mid = (lo + hi) >> 1; if (canMake(mid)) hi = mid; else lo = mid + 1; } return lo;}