Minimum Number of Days to Make m Bouquets — Binary Search on Answer [LC 1482]

Problem Statement#

LeetCode 1482 — Minimum Number of Days to Make m Bouquets · Difficulty: Medium

You have a garden of n flowers. bloomDay[i] is the day flower i blooms. To make one bouquet you need k adjacent bloomed flowers. Return the minimum number of days needed to make m bouquets, or -1 if it is impossible.

Constraints:

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

Example 1:

Input:  bloomDay = [1,10,3,10,2], m = 3, k = 1
Output: 3
Explanation: On day 3, flowers at indices 0,2,4 have bloomed (days 1,3,2 <= 3).
             Three individual bouquets are possible. Answer is 3.

Example 2:

Input:  bloomDay = [1,10,3,10,2], m = 3, k = 2
Output: -1
Explanation: We need 3*2 = 6 flowers but only have 5. Impossible.

Example 3:

Input:  bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
Output: 12
Explanation: On day 7: flowers [0,1,2,3,5,6] bloom → bouquet [0,1,2] and [3,?] fails (4 not bloomed).
             On day 12: flower 4 blooms too → [0,1,2] and [4,5,6] → 2 bouquets. Answer is 12.

Why This Problem Matters#

This is the canonical "binary search on the answer" problem — a template that appears constantly in FAANG interviews under different disguises: shipping packages (LC 1011), eating bananas (LC 875), splitting arrays (LC 410), and more. Once you understand why the answer space is monotone and how to write a feasible(d) check, you can crack an entire family of hard-looking problems in minutes.

The key FAANG insight being tested: the ability to transform a search problem into a decision problem. Instead of directly computing the minimum day, you ask "can we make m bouquets by day d?" and binary search on d. This reframing turns an O(n) brute-force over all possible days into an O(n log D) solution where D is the range of bloom days.

Interviewers at Amazon and Google commonly assign this problem to test whether candidates can identify the monotone property and construct the feasibility check correctly without hints.

The Core Insight#

The monotone property: if it is possible to make m bouquets by day d, then it is also possible by day d+1 (more flowers have bloomed, never fewer). This monotone structure makes the answer space perfect for binary search.

Search space: the answer must lie between min(bloomDay) (the earliest any flower can bloom) and max(bloomDay) (when all flowers have bloomed).

Feasibility check for a given day d: Walk through bloomDay left to right. Count consecutive flowers that have bloomed (bloomDay[i] <= d). Each time you accumulate k consecutive bloomed flowers, form a bouquet and reset the counter. If you form at least m bouquets, the day is feasible.

Impossible case: if m * k > n, there are not enough flowers regardless of the day — return -1 immediately. This O(1) check prevents searching on an infeasible problem.

Visual Dry Run#

Input: bloomDay = [7, 7, 7, 7, 12, 7, 7], m = 2, k = 3

Search range: lo = 7 (min), hi = 12 (max)

Verification for day 12: bloomed = [T,T,T,T,T,T,T]. Run [0..2]=3 flowers → bouquet 1. Run [3..3]=1 flower, reset at 4 which also blooms, [4..6]=3 flowers → bouquet 2. Total = 2 bouquets. Correct.

Feasibility walk-through for mid = 9:

Result: 1 bouquet < m=2, so day 9 is not feasible.

Common Mistakes#

1. Not checking impossibility upfront — if m * k > len(bloomDay), there are never enough flowers. Forgetting this check causes the binary search to return a wrong answer (usually max(bloomDay)) instead of -1.

2. Off-by-one in the search bounds — the lower bound is min(bloomDay), not 1. Starting at lo = 1 works but wastes iterations unnecessarily. The upper bound is max(bloomDay), not infinity.

3. Resetting consecutive count incorrectly — when a flower has NOT bloomed, reset the consecutive counter to 0. Forgetting the reset causes bouquets to span non-adjacent flowers.

4. Forming bouquets in the wrong order — flowers must be adjacent. Sorting bloomDay or picking flowers greedily across non-adjacent positions is wrong.

5. Integer overflow in the impossibility check — m * k can exceed 32-bit int range when m and k are both large. In Java or C++, cast to long before multiplying.

6. Using upper-mid vs lower-mid incorrectly — we are minimising the answer, so we use lower-mid (lo + hi) // 2 and set hi = mid on success. Using upper-mid and lo = mid is for maximisation problems.

7. Forgetting that the answer must be an actual bloom day — the minimum feasible day will always equal some bloomDay[i], because nothing changes between two consecutive bloom days. The binary search converges to exactly this value.

Solutions#

Python#

import math
 
def minDays(bloomDay: list[int], m: int, k: int) -> int:
    n = len(bloomDay)
 
    # Early exit: even if every flower is used, we cannot form m*k flowers
    if m * k > n:
        return -1
 
    def feasible(day: int) -> bool:
        """Check if we can form m bouquets of k consecutive bloomed flowers by 'day'."""
        bouquets = 0    # number of bouquets formed so far
        consecutive = 0 # count of consecutive bloomed flowers
 
        for bloom in bloomDay:
            if bloom <= day:
                consecutive += 1        # this flower has bloomed, extend the run
                if consecutive == k:    # completed one bouquet
                    bouquets += 1
                    consecutive = 0     # reset for the next bouquet
            else:
                consecutive = 0         # bloom not yet: break the consecutive run
 
        return bouquets >= m            # did we form enough bouquets?
 
    # Binary search on the answer (day value)
    lo, hi = min(bloomDay), max(bloomDay)
 
    while lo < hi:
        mid = lo + (hi - lo) // 2      # lower-mid for minimisation
        if feasible(mid):
            hi = mid                    # feasible: try an earlier day
        else:
            lo = mid + 1               # not feasible: need more days
 
    return lo                           # lo == hi == minimum feasible day

JavaScript#

function minDays(bloomDay, m, k) {
    const n = bloomDay.length;
 
    // If total flowers needed exceed available flowers, impossible
    if (m * k > n) return -1;
 
    // Check whether we can form m bouquets of k consecutive flowers by 'day'
    function feasible(day) {
        let bouquets = 0;     // bouquets formed
        let consecutive = 0;  // consecutive bloomed flowers in current run
 
        for (const bloom of bloomDay) {
            if (bloom <= day) {
                consecutive++;              // flower has bloomed, extend the run
                if (consecutive === k) {    // completed a bouquet
                    bouquets++;
                    consecutive = 0;        // reset the run counter
                }
            } else {
                consecutive = 0;            // flower not yet bloomed, break the run
            }
        }
 
        return bouquets >= m;               // enough bouquets formed?
    }
 
    // Binary search on the answer space [min(bloomDay), max(bloomDay)]
    let lo = Math.min(...bloomDay);
    let hi = Math.max(...bloomDay);
 
    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2); // lower-mid: minimising
 
        if (feasible(mid)) {
            hi = mid;           // feasible: try to find an earlier day
        } else {
            lo = mid + 1;       // not feasible: need at least mid+1 days
        }
    }
 
    return lo;                  // converged to minimum feasible day
}

Complexity Analysis#

With n up to 10^5 and D up to 10^9, the binary search runs at most log₂(10^9) ≈ 30 iterations, each costing O(n). Total: O(30n) ≈ O(n log D), which handles all constraints comfortably.

Follow-up Questions#

1. Why is the answer always a bloomDay value? — Between two consecutive distinct bloom days, no new flowers bloom so feasibility does not change. The binary search converges to the smallest bloomDay that is feasible.

2. Can k be larger than n? — If k > n, then m * k > n (since m >= 1), and the early exit returns -1 before the binary search even starts.

3. What if all bloom days are the same? — e.g. [5,5,5,5,5], m=1, k=3. lo = hi = 5 from the start. The loop does not execute and we return 5 directly. Correct.

4. How does this relate to LC 875 (Koko Eating Bananas)? — Both binary search on a continuous answer space and use a greedy feasibility check. The key structural difference: Koko minimises speed (monotone decreasing feasibility as speed increases), while here we minimise days (monotone increasing feasibility as days increase). The binary search template is identical.

5. What if bouquets didn't need to be adjacent? — Then the feasibility check becomes: count all bloomed flowers, check if count >= m * k. No need to track consecutive runs. The binary search structure stays the same.

This Pattern Solves#

• LC 1482 — Minimum Days to Make m Bouquets (this problem)
• LC 875 — Koko Eating Bananas (minimise rate)
• LC 1011 — Capacity to Ship Packages (minimise capacity)
• LC 410 — Split Array Largest Sum (minimise max subarray sum)
• LC 1552 — Magnetic Force Between Two Balls (maximise minimum distance)
• LC 2064 — Minimized Maximum of Products (minimise max)
• Any problem of the form: "find the minimum X such that a greedy check with X passes"

Key Takeaway#

Binary search on the answer transforms "find the optimal value" into "is this value feasible?" The key steps are: (1) identify that the answer space is monotone (feasibility changes in one direction only), (2) set lo and hi to the tightest valid bounds, (3) write a greedy O(n) feasibility check, and (4) use lower-mid with hi = mid on success (for minimisation). This template solves a huge class of interview problems and is one of the most powerful binary search patterns to master.

Key Takeaways#

• LC 1482 is a binary search on answer problem asked by Google and Amazon; the insight is searching the day-space [min(bloomDay), max(bloomDay)] rather than the array.
• Feasibility is monotone: waiting more days can only make it easier (or equally easy) to form bouquets — this monotonicity is the prerequisite for binary search.
• The feasibility check is a greedy O(n) scan: count consecutive bloomed flowers, reset the counter when a gap breaks the run, and increment bouquet count when k consecutive flowers are found.
• Return -1 immediately when m * k > n — there are not enough flowers to ever form the required bouquets regardless of how long you wait.
• Set search bounds to [min(bloomDay), max(bloomDay)] — the answer must be one of the actual bloom days since feasibility only changes when a new flower blooms.
• Time complexity is O(n log D) where D = max - min of bloomDay: up to 30 binary search iterations, each O(n).
• This template solves the entire class of "find minimum day/time/rate such that a greedy check passes" problems including LC 875, LC 1011, and LC 410.