Minimum Number of Days to Make m Bouquets

You look after a flower garden — n flowers planted in a single row. The i-th flower blooms on day bloomDay[i], stays open forever after, and can be cut for exactly one bouquet.

You have an order for m bouquets. Each bouquet needs exactly k adjacent flowers — side-by-side in the row, no gaps, and no flower shared between bouquets.

Return the minimum number of days you must wait until the garden can supply all m bouquets. If it is impossible no matter how long you wait, return -1.

Hints

· Stuck? Reveal one nudge at a time.

Waiting never hurts: if the garden can fill the order by day d, it can certainly fill it by day d + 1. What shape does that give the sequence of yes/no answers across the calendar?

Freeze a single day d and ask a much simpler question: how many bouquets can be cut using only flowers with bloomDay[i] <= d? One left-to-right pass suffices — grow a streak of adjacent bloomed flowers, and every time it reaches k, cut a bouquet and reset the streak.

The answers over days form NO NO ... NO YES YES ... YES — binary search [min(bloomDay), max(bloomDay)] for the first YES. Handle the impossible case up front: if m * k > n, return -1 (compute the product in 64-bit).

Common doubts

Nothing changes between bloom days — the set of open flowers only grows on a day equal to some bloomDay[i]. Feasibility can therefore only flip from no to yes on a bloom day, and binary search over the full range still converges exactly onto that first flip.

Within a run of s consecutive bloomed flowers you can fit at most s / k (floor) disjoint bouquets, and the greedy reset achieves exactly that. Delaying a cut can only waste flowers at the front of the run, never gain any.

No on both counts — each flower is used in exactly one bouquet, and the k flowers must be adjacent, so an unbloomed flower breaks the streak and separates runs.

It is the only impossible case — with enough waiting every flower blooms, so any garden with at least m * k flowers eventually works. Beware the product: it can reach 10^11, which overflows 32-bit integers in C++.

Interview follow-ups

· What an interviewer asks next.

Adjacency was the whole difficulty. Without it you just need the day by which m * k flowers have bloomed — the (m * k)-th smallest bloom day, found by sorting in O(n log n) or quickselect in average O(n).

Any minimize-the-answer problem with a monotone feasibility check: Koko Eating Bananas (search the eating speed), Find the Smallest Divisor Given a Threshold (search the divisor), Capacity to Ship Packages Within D Days (search the capacity), Split Array Largest Sum (search the max subarray sum). Only the O(n) checker changes.

Yes — process flowers in increasing bloom-day order and merge adjacent bloomed segments (union-find or a length map), tracking how many bouquets the merged segments yield; the answer is the bloom day whose merge first reaches m bouquets. It runs in O(n log n) and makes a great discussion of trade-offs versus the binary-search approach.

Fun facts

With bloom days up to 10^9, the binary search asks at most ~30 yes/no questions — you interrogate a billion-day calendar for the cost of scanning the garden thirty times.
The skeleton here — monotone feasibility plus binary search on the value space — is one of the most reused patterns in interviews: the same six lines solve Koko Eating Bananas and Capacity to Ship Packages Within D Days with a different one-pass check swapped in.

Asked at

GoogleAmazonMicrosoftFlipkart

Frequently Sometimes Occasionally

Example 1

Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
Output: 3
Each bouquet needs just 1 flower, so we need any 3 bloomed flowers. Writing x for bloomed and _ for not yet:
After day 1: [x, _, _, _, _] — 1 bouquet.
After day 2: [x, _, _, _, x] — 2 bouquets.
After day 3: [x, _, x, _, x] — 3 bouquets. Day 3 is the first day the order can be filled.

Example 2

Input: bloomDay = [1,10,3,10,2], m = 3, k = 2
Output: -1
3 bouquets of 2 flowers each need 6 flowers, but the garden only has 5. No amount of waiting helps — return -1.

Example 3

Input: bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
Output: 12
After day 7 the garden looks like [x, x, x, x, _, x, x]. The first four flowers give one bouquet, but the remaining bloomed flowers are split by the unbloomed one — no second bouquet of 3 adjacent flowers. After day 12 every flower is open and both bouquets are easy, so the answer is 12.

Constraints

- bloomDay.length == n - 1 <= n <= 10^5 - 1 <= bloomDay[i] <= 10^9 - 1 <= m <= 10^6 - 1 <= k <= n

Most search problems ask you to search a collection. This one asks you to search time itself: the array never changes — only the calendar does. The arc: see why waiting can only help, turn a fixed day into a one-pass counting question, then binary search the calendar for the first day that says yes.

Prerequisites

Before you start

· Concepts used directly in the solution.

Binary search on a value range. Searching an answer space like days 1 to 10^9 — not array indices — by halving a lo..hi window.

Monotone predicates. A yes/no question whose answers look like NO NO NO YES YES YES — it flips exactly once, so the first YES is findable by binary search.

Greedy counting in one pass. Scanning an array once while maintaining a running streak counter.

Understand the problem

In plain English: flowers bloom on given days, a bouquet is k adjacent bloomed flowers, every flower is used at most once — find the earliest day on which m disjoint bouquets exist.

Formally: find the minimum d such that the positions i with bloomDay[i] <= d, read left to right, contain at least m disjoint runs of k consecutive bloomed flowers. If m * k > n, no such d exists — return -1.

Worked example — bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3

after day 7 :  x x x x _ x x     runs: 4 and 2
               [--1--]?          4 // 3 = 1 bouquet, 2 // 3 = 0  → only 1, not enough
after day 12:  x x x x x x x     run: 7
               [--1--][--2--]    7 // 3 = 2 bouquets ✓
answer: 12

Clarifying questions

A senior candidate pins down the rules of the garden before writing a line of code.

Questions to ask first

· Signals seniority before you write a line of code.

Bouquet rules

“Must the k flowers in one bouquet be adjacent in the row?”

Yes — this is the heart of the problem. Without adjacency the answer is simply the (m·k)-th smallest bloom day.

“Can a flower belong to two bouquets?”

No — each flower is cut exactly once, so bouquets are disjoint runs.

Input validity

“Can m times k exceed the number of flowers?”

Yes, and then the answer is -1 — worth handling up front before any searching.

“Are bloom days always positive integers?”

Yes, at least 1 — so the search window min(bloomDay) to max(bloomDay) is well-defined.

Constraints and scale

“How large can bloomDay[i] get?”

Up to 10^9 — simulating the garden day by day is hopeless, which is a strong hint to search days cleverly instead.

“How large is n?”

Up to 10^5 — an O(n) check per probed day is fine; an O(n) check per distinct day is not.

The ideal opening — say it like this

Before I code, let me confirm the bouquet rules: the k flowers must be adjacent, and each flower is used in at most one bouquet.

If m times k exceeds n, it is impossible and I should return -1 — I will check that first, in 64-bit since the product can reach 10^11.

Bloom days go up to a billion, so instead of simulating days I will binary search the day, using a linear feasibility check.

Key observations

1Aha

Time only helps — feasibility is monotone

If the order can be filled by day d, every flower open on day d is still open on day d + 1, so it can be filled then too. Across the calendar the answers form a single flip:

day:      1   2   3   4   5   6   7  ...
can make? NO  NO  NO  YES YES YES YES ...
                      ^ the answer is the first YES

One flip means binary search applies — not on the array, but on the day.

2Aha

For a fixed day, counting bouquets is one greedy pass

Freeze a day d. A flower is open iff bloomDay[i] <= d. Scan left to right keeping a streak of consecutive open flowers; the moment it reaches k, cut a bouquet and reset the streak to 0; an unbloomed flower also resets it. A run of s open flowers yields exactly s // k bouquets, and cutting as early as possible never hurts — so this greedy count is the maximum. The check is O(n).

3Aha

Search the calendar, not the garden

The answer lies in [min(bloomDay), max(bloomDay)] — before the first bloom nothing is possible, and by the last bloom everything that will ever be possible already is. Binary search that window for the first YES: about log2(10^9) ≈ 30 probes, each an O(n) scan. Handle m * k > n up front with -1.

Brute force vs optimal

Let d be the number of distinct bloom days and D the largest bloom day.

	Brute force	Optimal
Idea	try each distinct bloom day in order	binary search the day, greedy check
Time	O(n · d)	O(n log D)
Space	O(d)	O(1)

Full, runnable code for both lives in the Approaches selector below.

Summary

Key takeaway

When the answer is a number and you can cheaply check would this value work? — with the answers monotone across the range — binary search the answer space instead of the input. The exact same skeleton solves Koko Eating Bananas, Find the Smallest Divisor Given a Threshold, and Capacity to Ship Packages Within D Days; only the feasibility check changes.

if m * k > n: return -1
lo, hi = min(bloomDay), max(bloomDay)
while lo < hi:
    mid = (lo + hi) / 2
    if canMake(mid):  hi = mid        # mid works — try to wait less
    else:             lo = mid + 1    # too early — must wait longer
return lo                             # the first day the calendar says yes