Minimum Number of Days to Make m Bouquets
Medium Binary search on the answer
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Flower i blooms on bloomDay[i]. A bouquet needs k adjacent bloomed flowers. Return the earliest day you can make m bouquets, or -1.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the earliest day you can make m bouquets of k neighbouring flowers.
Why this works: waiting longer never hurts, so binary search the day and count bouquets from runs of bloomed flowers.
Example: bloomDay [1, 10, 3, 10, 2], m = 3, k = 1
day 3: bloomed 1, 3, 2 → 3 bouquets ✓day 2: only 2 bouquets ✗ → answer 3
✦Hints open one at a time
↗Approach
Binary search d between the smallest and largest bloom day. Feasibility: walk the array, extend the current run when bloomDay[i] <= d, and cut a bouquet whenever the run reaches k.
</>Solution (Java)
class Solution {
public int minDays(int[] bloomDay, int m, int k) {
if ((long) m * k > bloomDay.length) return -1;
int lo = Integer.MAX_VALUE, hi = 0;
for (int d : bloomDay) {
lo = Math.min(lo, d);
hi = Math.max(hi, d);
}
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (bouquets(bloomDay, mid, k) >= m) hi = mid;
else lo = mid + 1;
}
return lo;
}
private int bouquets(int[] bloomDay, int day, int k) {
int made = 0, run = 0;
for (int d : bloomDay) {
if (d <= day) {
if (++run == k) { made++; run = 0; } // cut a bouquet
} else {
run = 0;
}
}
return made;
}
}!Common mistake
Computing m * k in int — both can be 10^5 / 10^6 and overflow. Use long.
- Time: O(n log D).
- Space: O(1).