The first day enough adjacent flowers are open
Flowers stand in a row; flower i opens on day bloom[i] and stays open. A bouquet takes
k adjacent open flowers, and each flower can be used in one bouquet only. Return the earliest
day on which m bouquets can be made, or −1 if that never happens.
Examples
| Input | Output | Why |
|---|---|---|
bloom = [1, 10, 3, 10, 2], m = 3, k = 1 | 3 | By day 3, flowers 0, 2 and 4 are open. |
bloom = [1, 10, 3, 10, 2], m = 3, k = 2 | -1 | Six flowers are needed and there are five. |
bloom = [7, 7, 7, 7, 12, 7, 7], m = 2, k = 3 | 12 | On day 7 only one run of three exists; day 12 joins the gap. |
Constraints
- 1 ≤ n ≤ 10⁵
- 1 ≤ bloom[i] ≤ 10⁹
- 1 ≤ m ≤ 10⁶, 1 ≤ k ≤ n
Hints
Hint 1
If m × k is more than the number of flowers, the answer is −1 whatever the days are.
Hint 2
For a fixed day d, how many bouquets can you make? Scan left to right, counting consecutive open flowers, and cut a bouquet each time the count reaches k.
Hint 3
A later day opens more flowers and never closes one, so the count never falls. Search the first day with count ≥ m.
Where people lose marks
- Computing m × k in 32 bits: 10⁶ × 10⁵ overflows.
- Counting all open flowers rather than runs of adjacent ones.
- Not resetting the run to zero after cutting a bouquet, which lets one flower serve two bouquets.
Dry run on [7,7,7,7,12,7,7],2,3
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 4lo7hi12
2 bouquets of 3 need 6 of the 7 flowers, so an answer exists. Search days 7 to 12.
-
Step 2 / 4lo7mid9hi12
Day 9: open = ■■■■□■■, 1 run of 3, not enough for 2. 9 fails, so does everything below it: lo = 10.
-
Step 3 / 4lo10mid11hi12
Day 11: open = ■■■■□■■, 1 run of 3, not enough for 2. 11 fails, so does everything below it: lo = 12.
-
Step 4 / 4answer12
lo = hi = 12: the first day with 2 bouquets.
How to think about it
First the impossible case: m bouquets of k flowers need m × k
flowers, so if m × k > n return −1 (compute it in 64 bits: both can be large). Otherwise, by the
last bloom day every flower is open and n adjacent flowers give at least m bouquets, so
an answer exists.
For a fixed day d, the best number of bouquets comes from one greedy scan: count open flowers in
a run, and whenever the run reaches k, make a bouquet and restart the count. Taking the leftmost
k flowers of a run never costs a bouquet, because any bouquet that uses a later window could be
shifted left without colliding.
Days only open flowers, so bouquets(d) never decreases as d grows, and
bouquets(d) ≥ m switches from false to true once. Binary search on d from
min(bloom) to max(bloom); each check is O(n).
The check is the only part that changes between problems in this pattern: here a run counter, for ships a greedy loader, for rates a sum of ceilings. The search around it stays the same.
Complexity. Time O(n log(max − min)) · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def min_days(bloom, m, k):
if m * k > len(bloom):
return -1
def bouquets(day): # greedy: cut a bouquet whenever a run reaches k
made = run = 0
for b in bloom:
run = run + 1 if b <= day else 0
if run == k:
made += 1
run = 0
return made
lo, hi = min(bloom), max(bloom) # by the last day everything is open
while lo < hi:
mid = (lo + hi) // 2
if bouquets(mid) >= m:
hi = mid
else:
lo = mid + 1
return lo#include <vector>
#include <algorithm>
int solve(const std::vector<int>& bloom, int m, int k) {
if ((long long)m * k > (long long)bloom.size()) return -1;
auto bouquets = [&](int day) {
int made = 0, run = 0;
for (int b : bloom) {
run = b <= day ? run + 1 : 0;
if (run == k) { ++made; run = 0; } // cut a bouquet
}
return made;
};
int lo = *std::min_element(bloom.begin(), bloom.end());
int hi = *std::max_element(bloom.begin(), bloom.end());
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (bouquets(mid) >= m) hi = mid; else lo = mid + 1;
}
return lo;
}class Solution {
private int bouquets(int[] bloom, int k, int day) {
int made = 0, run = 0;
for (int b : bloom) {
run = b <= day ? run + 1 : 0;
if (run == k) { made++; run = 0; } // cut a bouquet
}
return made;
}
public int minDays(int[] bloom, int m, int k) {
if ((long) m * k > bloom.length) return -1;
int lo = Integer.MAX_VALUE, hi = 0;
for (int b : bloom) { lo = Math.min(lo, b); hi = Math.max(hi, b); }
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (bouquets(bloom, k, mid) >= m) hi = mid; else lo = mid + 1;
}
return lo;
}
}function minDays(bloom, m, k) {
if (m * k > bloom.length) return -1; // exact in doubles
const bouquets = day => {
let made = 0, run = 0;
for (const b of bloom) {
run = b <= day ? run + 1 : 0;
if (run === k) { made++; run = 0; } // cut a bouquet
}
return made;
};
let lo = Math.min(...bloom), hi = Math.max(...bloom);
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (bouquets(mid) >= m) hi = mid; else lo = mid + 1;
}
return lo;
}fn solve(bloom: &[i64], m: i64, k: i64) -> i64 {
if m * k > bloom.len() as i64 {
return -1;
}
let bouquets = |day: i64| -> i64 {
let (mut made, mut run) = (0, 0);
for &b in bloom {
run = if b <= day { run + 1 } else { 0 };
if run == k {
made += 1; // cut a bouquet
run = 0;
}
}
made
};
let (mut lo, mut hi) = (*bloom.iter().min().unwrap(), *bloom.iter().max().unwrap());
while lo < hi {
let mid = lo + (hi - lo) / 2;
if bouquets(mid) >= m { hi = mid } else { lo = mid + 1 }
}
lo
}solve :: [Int] -> Int -> Int -> Int
solve bloom m k
| m * k > length bloom = -1
| otherwise = go (minimum bloom) (maximum bloom)
where
-- greedy: cut a bouquet whenever a run of open flowers reaches k
bouquets day = fst (foldl step (0, 0) bloom)
where
step (made, run) b
| b > day = (made, 0)
| run + 1 == k = (made + 1, 0)
| otherwise = (made, run + 1)
go lo hi
| lo >= hi = lo
| bouquets mid >= m = go lo mid
| otherwise = go (mid + 1) hi
where mid = lo + (hi - lo) `div` 2Variants to try
- Search only over the distinct bloom days, sorted: same number of steps, and the answer is always one of them.
- Each bouquet may take any k open flowers, adjacent or not: the k-th smallest bloom day of the (m·k) needed, with no search.
Next problems
Smallest ship that clears the backlog in D days
When the answer is a number and "is X enough?" is easy to check, search over answers rather than over data.
Open the problem → Medium20 minThe slowest rate that clears every queue in time
At rate k a queue of p items takes ⌈p / k⌉ hours. The total only falls as k rises, so search for the smallest k that fits the deadline.
Open the problem → Medium20 minEarliest time a fleet completes its trips
By time t a vehicle with round-trip time x has finished ⌊t / x⌋ trips. The fleet total never falls as t grows: search the first t that reaches the target.
Open the problem →Write a solution and run it against the real test table.
Keep going
Smallest ship that clears the backlog in D days
When the answer is a number and "is X enough?" is easy to check, search over answers rather than over data.
Open the problem → Medium20 minThe slowest rate that clears every queue in time
At rate k a queue of p items takes ⌈p / k⌉ hours. The total only falls as k rises, so search for the smallest k that fits the deadline.
Open the problem → Medium20 minEarliest time a fleet completes its trips
By time t a vehicle with round-trip time x has finished ⌊t / x⌋ trips. The fleet total never falls as t grows: search the first t that reaches the target.
Open the problem → Binary searchThe pattern behind it
Search the answer, not the array: halve a monotone predicate until one candidate is left.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.