Minimum Number of Days to Make m Bouquets

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}