← DSA Atlas
Dedicated problem page · #1482

Minimum Number of Days to Make m Bouquets

MediumBinary SearchBinary search on days with a greedy bouquet countBinary search on the answer
Solve on LeetCode ↗
1482
MediumBinary SearchBinary search on the answerBinary search on days with a greedy bouquet count

Minimum Number of Days to Make m Bouquets

You are given an integer array bloomDay where bloomDay[i] is the day the i-th flower blooms, plus integers m and k. To make one bouquet you need k adjacent flowers that have already bloomed. Return the minimum number of days you must wait to make m bouquets; if it is impossible to make that many, return -1.

Open official problem prompt ↗
In plain English

Find the earliest day on which enough adjacent flowers have bloomed to assemble m bouquets of k flowers each.

Picture it like this

Watering a garden and waiting: each extra day opens more blossoms and never closes any, so you look for the first sunrise on which you can finally cut all the bouquets you need.

Example
Input
bloomDay = [1,10,3,10,2], m = 3, k = 1
Output
3
Why
Each bouquet needs only 1 flower. By day 3 the flowers with bloomDay 1, 3, and 2 have bloomed - three flowers, hence three single-flower bouquets; day 2 yields only two.
Constraints
bloomDay.length == n1 <= n <= 10^51 <= bloomDay[i] <= 10^91 <= m <= 10^61 <= k <= n
Pattern lesson

See the pattern, then code

Binary search on days with a greedy bouquet count
Recognition clue

You minimize a number of days subject to producing m bouquets, and given a day it is easy to count achievable bouquets - a textbook binary-search-on-the-answer setup.

↗
Binary Search

Sorted data or a monotonic true/false condition over a possible answer.. Waiting more days never reduces how many bouquets you can form, so feasibility is monotone in the day count. For a fixed day, scan left to right counting runs of k consecutive bloomed flowers; each completed run is one bouquet.

New words, made simpleKnow these before the algorithm
Binary search on the answer
Searching over candidate day counts and testing feasibility, not over array indices.
Adjacent run
A maximal stretch of consecutive already-bloomed flowers, from which floor(run/k) bouquets can be cut.
Monotone predicate
The property that if m bouquets are possible by day D, they are possible by any later day too.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Scan every day from 1 upward

bloomDay can reach 10^9, so scanning day by day is hopeless.

Try each day and count bouquets until reaching m.

Time O(n * max(bloomDay))Space O(1)
Best choiceBinary search on the day

A handful of linear scans over the array; efficient even for huge day values.

Bound days by [min, max] of bloomDay and binary search, using a greedy adjacency count as the test.

Time O(n log(max(bloomDay)))Space O(1)
The rule we keep true

Invariant

hi is always a day by which m bouquets are achievable, and lo-1 is always a day by which they are not, so the earliest feasible day lies in [lo, hi].

Why this is correct

Reasoning

Counting bouquets for a fixed day is exact: a maximal run of r consecutive bloomed flowers yields floor(r/k) bouquets, and resetting the counter at each unbloomed flower or completed bouquet enforces adjacency. Since flowers only ever bloom as days pass, more days never lower the bouquet count, so the 'can make m bouquets' predicate is monotone. Binary search finds the day where it first becomes true. The early m*k > n check handles genuine impossibility, since you can never harvest more than floor(n/k) bouquets total.

The algorithm in three movesSay these aloud before coding
1If m*k exceeds the number of flowers, return -1 immediately

m*k=3 <= 5 -> possible

2Set lo = min(bloomDay) and hi = max(bloomDay) as day bounds

day=3: bloomed at idx 0,2,4 -> 3 runs of length 1 -> 3 bouquets >=3 feasible

3For a candidate day, greedily count bouquets from runs of k adjacent bloomed flowers

day=2: bloomed idx 0,4 -> 2 bouquets <3 -> lo moves up; answer 3

4If bouquets >= m the day is feasible so shrink hi = mid; else lo = mid+1

5Return lo, the earliest feasible day

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
101
32
103
24
1 · Readm*k = 3, n = 5
2 · AskEnough flowers to ever make m bouquets?
3 · Update state3 <= 5
4 · ResultPossible; proceed
Key takeaway

By day 3 the highlighted flowers (bloomDay 1, 3, 2) have opened, giving three single-flower bouquets.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-4Impossibility guard

    If m bouquets would need more than n flowers, no day can ever satisfy it, so return -1.

  2. 2
    Lines 5-15Greedy bouquet counter

    Walk the array counting consecutive bloomed flowers; every time the run reaches k, bank a bouquet and reset the run.

  3. 3
    Lines 16Day bounds

    The earliest useful day is the minimum bloom day; by the maximum bloom day all flowers are open.

  4. 4
    Lines 17-22Lower-bound binary search

    Feasible days push hi down; infeasible days push lo up, converging on the first feasible day.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • m*k > n (return -1)
  • k == 1 (each bloomed flower is its own bouquet)
  • All flowers share the same bloom day
  • m*k == n exactly (need every flower, so answer is max(bloomDay))
!

Common beginner mistakes

  • Forgetting the m*k > n impossibility check and returning a wrong day
  • Not resetting the adjacency counter when a flower has not bloomed, which would count non-adjacent flowers
  • Watch for m*k overflow in languages with fixed-width ints (safe in Python)
  • Using lo <= hi with hi=mid, causing an infinite loop
Check your understanding

Why must the adjacency counter reset both when a flower is not yet bloomed and when a bouquet completes?

More in Binary Search

#33Search in Rotated Sorted ArrayBinary search on a rotated array#153Find Minimum in Rotated Sorted ArrayBinary search for the rotation point#875Koko Eating BananasBinary search on the answer#4Median of Two Sorted ArraysBinary search on the partition#34Find First and Last Position of ElementLower-bound binary search on both ends#35Search Insert PositionLower-bound binary search