The challenge
Find the earliest day when m bouquets can be made, each using k adjacent flowers without reuse.
Nonempty positive bloom days ≤ 10⁹; m ≥ 1 and k ≥ 1. Return −1 if m*k exceeds the number of flowers.
Example
[1, 10, 3, 10, 2], m = 3, k = 1 → day 3.
Use the walkthrough below to inspect the input and each state change.
See Earliest bouquet day, step by step
Inspect the comparison, the invariant, and the next boundary.
Answer-space searchk = 1 · m = 3
Tested candidate / qualifying inputResolved positionParameters shown above
- Left
- 1
- Middle
- —
- Right
- 10
Step 01 / 5
Search the answer range
The candidate is a day, rather than an input index. Keep the smallest feasible value.
left = 1; right = 10Recorded result so far
Not resolved
View exact input
Input: [1,10,3,10,2] · k = 1 · m = 3
Put it into code
A flower is available on day d when bloom[i] ≤ d. Count disjoint adjacent runs; availability can only improve on later days.
Indices are zero-based. C++ uses C++17 or later.
def minimum_days(bloom, m, k):
# Nonempty positive bloom days; m >= 1, k >= 1.
if m * k > len(bloom):
return -1
left, right = min(bloom), max(bloom)
while left < right:
mid = left + (right - left) // 2
bouquets, run = 0, 0
for day in bloom:
if day > mid:
run = 0
else:
run += 1
if run == k:
bouquets += 1
run = 0
if bouquets >= m:
right = mid
else:
left = mid + 1
return left#include <algorithm>
#include <vector>
int minimum_days(const std::vector<int>& bloom, int m, int k) {
if (1LL * m * k > static_cast<long long>(bloom.size())) return -1;
int left = *std::min_element(bloom.begin(), bloom.end());
int right = *std::max_element(bloom.begin(), bloom.end());
while (left < right) {
int mid = left + (right - left) / 2, bouquets = 0, run = 0;
for (int day : bloom) {
if (day > mid) run = 0;
else if (++run == k) { ++bouquets; run = 0; }
}
if (bouquets >= m) right = mid;
else left = mid + 1;
}
return left;
}