Minimum Number of Days to Make m Bouquets — Medium Problem & Solution

Problem statement

Flower i blooms on day bloomDay[i] and stays bloomed. One bouquet uses k adjacent bloomed flowers, and each flower can be used in at most one bouquet.

Return the earliest day on which m bouquets can be made, or -1 if it is impossible.

Example 1

Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
Output: 3
Explanation: By day 3 the flowers at 0, 2 and 4 have bloomed.

Example 2

Input: bloomDay = [1,10,3,10,2], m = 3, k = 2
Output: -1
Explanation: Only 5 flowers exist but 6 are needed.

Example 3

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

Constraints

• 1 <= bloomDay.length <= 100000
• 1 <= bloomDay[i] <= 1000000000
• 1 <= m <= 1000000
• 1 <= k <= bloomDay.length

How to solve Minimum Number of Days to Make m Bouquets

Binary search the answer. For a fixed day, the maximum number of bouquets is obtained greedily: walk the array and close a bouquet every time k consecutive bloomed flowers accumulate. That count only grows as the day advances.

Approach

1. Reject outright when m · k > n.
2. Set the search range to the minimum and maximum bloom days.
3. can(day): count runs of flowers with bloomDay[i] <= day, taking floor(runLength / k) bouquets from each — the reset-on-k loop does exactly that.
4. Binary search the smallest feasible day.

Why it works

Greedy cutting is optimal within a run of length L: any arrangement of adjacent groups of k inside it yields at most floor(L / k) bouquets, and cutting from the left achieves that. Since a later day only turns more flowers bloomed, runs can only lengthen and merge, so the bouquet count is non-decreasing — the predicate is monotone.

Complexity

• Time — O(n log D) where D is the bloom-day range
• Space — O(1)

Pitfalls

• m · k reaches 10^6 · 10^5 = 10^11 — the impossibility check needs 64-bit arithmetic.
• A run must reset on an unbloomed flower, otherwise non-adjacent flowers get combined.
• Searching from day 1 rather than the minimum bloom day still works but wastes iterations.

Reference solution

Python

from typing import List

def minDays(bloomDay: List[int], m: int, k: int) -> int:
    n = len(bloomDay)
    if m * k > n:
        return -1
    lo, hi = min(bloomDay), max(bloomDay)

    def can(day: int) -> bool:
        made = run = 0
        for b in bloomDay:
            if b <= day:
                run += 1
                if run == k:
                    made += 1
                    run = 0
            else:
                run = 0
        return made >= m

    while lo < hi:
        mid = (lo + hi) // 2
        if can(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

JavaScript

var minDays = function(bloomDay, m, k) {
    var n = bloomDay.length;
    if (m * k > n) return -1;
    var lo = bloomDay[0], hi = bloomDay[0], i;
    for (i = 1; i < n; i++) {
        if (bloomDay[i] < lo) lo = bloomDay[i];
        if (bloomDay[i] > hi) hi = bloomDay[i];
    }
    var can = function(day) {
        var made = 0, run = 0;
        for (var j = 0; j < n; j++) {
            if (bloomDay[j] <= day) {
                run++;
                if (run === k) { made++; run = 0; }
            } else run = 0;
        }
        return made >= m;
    };
    while (lo < hi) {
        var mid = Math.floor((lo + hi) / 2);
        if (can(mid)) hi = mid; else lo = mid + 1;
    }
    return lo;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Minimum Number of Increments on Subarrays to Form a Target Array Medium
• Find the Winner of an Array Game Medium
• Queries on a Permutation With Key Medium
• Corporate Flight Bookings Medium
• Find the Winner of the Circular Game Medium
• Longest Subsequence With Limited Sum Medium