Minimum Days To Make M Bouquets

Minimum Days to Make m Bouquets – A Complete Guide

Finding the minimum days to make m bouquets is a classic algorithmic challenge that appears in coding interviews and competitive programming platforms. The problem asks: given an array where each element represents the day on which a particular flower blooms, what is the earliest day on which you can pick enough adjacent flowers to form m bouquets, each bouquet requiring k consecutive bloomed flowers? If it is impossible to make the required bouquets, the answer is –1.

This article walks you through the intuition, the binary‑search solution, step‑by‑step implementation details, complexity analysis, and frequently asked questions. By the end, you’ll be able to explain the approach confidently and apply it to similar “threshold” problems.

Table of Contents

3. • 3.1 Helper Function: Can We Make m Bouquets in day Days?
   • 3.2 Binary Search Over the Answer Space

Problem Statement <a name="problem-statement"></a>

You are given:

• An integer array bloomDay of length n, where bloomDay[i] is the day (1‑indexed) on which the i‑th flower blooms.
• Two integers m and k:
  • m – the number of bouquets you need to make.
  • k – the number of adjacent bloomed flowers required for each bouquet.

Return the minimum day such that you can make at least m bouquets. If it is impossible, return -1.

Constraints (typical)

• 1 ≤ n ≤ 10⁵
• 1 ≤ bloomDay[i] ≤ 10⁹
• 1 ≤ m ≤ 10⁶
• 1 ≤ k ≤ n

Why Binary Search? <a name="why-binary-search"></a>

The answer (the earliest feasible day) is monotonic:

• If you can make m bouquets on day d, you can also make them on any later day d' > d because more flowers will have bloomed.
• Conversely, if you cannot make m bouquets on day d, you certainly cannot on any earlier day d' < d.

This monotonic property lets us apply binary search on the answer space (the range of possible days) instead of checking each day linearly, which would be O(n·max(bloomDay)) and infeasible for large inputs That alone is useful..

Step‑by‑Step Solution <a name="step-by-step-solution"></a>

3.1 Helper Function: Can We Make m Bouquets in day Days? <a name="helper-function"></a>

Define a function possible(day) that returns True if we can form at least m bouquets by the given day, otherwise False Most people skip this — try not to..

Algorithm for possible(day):

1. Initialize bouquets = 0 and consecutive = 0.
2. Iterate through bloomDay:
   • If bloomDay[i] ≤ day, the flower has bloomed → increment consecutive.
   • Else, reset consecutive = 0 (a non‑bloomed flower breaks adjacency).
   • Whenever consecutive == k, we have enough for one bouquet:
     • Increment bouquets.
     • Reset consecutive = 0 (flowers used in a bouquet cannot be reused).
   • Early exit: if bouquets >= m, return True.
3. After the loop, return bouquets >= m.

This runs in O(n) time and O(1) extra space.

3.2 Binary Search Over the Answer Space <a name="binary-search"></a>

• Low bound (left): the minimum bloom day in the array (min(bloomDay)). No answer can be smaller because at least one flower must have bloomed.
• High bound (right): the maximum bloom day (max(bloomDay)). Beyond this day all flowers have bloomed, so if a solution exists it will be ≤ right.
• While left ≤ right:
  • Compute mid = left + (right - left) // 2.
  • If possible(mid) is True, we can try to find an earlier feasible day → set right = mid - 1 and remember mid as a candidate answer.
  • Else, we need more days → set left = mid + 1.
• After the loop, if we never found a feasible day, return -1; otherwise return the stored candidate.

Because each iteration halves the search interval, the binary search runs in O(log (range)) time, where range = max(bloomDay) - min(bloomDay) + 1 Easy to understand, harder to ignore. Turns out it matters..

Pseudocode <a name="pseudocode"></a>

function minDays(bloomDay, m, k):
    if m * k > length(bloomDay):
        return -1                     // impossible even if all flowers bloom

    left  = min(bloomDay)
    right = max(bloomDay)
    answer = -1

    while left <= right:
        mid = left + (right - left) // 2
        if possible(bloomDay, mid, m, k):
            answer = mid
            right = mid - 1          // try to go lower
        else:
            left = mid + 1           // need more days

Short version: it depends. Long version — keep reading.

    return answer

function possible(bloomDay, day, m, k):
    bouquets = 0
    consecutive = 0
    for bloom in bloomDay:
        if bloom <= day:
            consecutive += 1
            if consecutive == k:
                bouquets += 1
                if bouquets == m:
                    return True
                consecutive = 0      // reset for next bouquet
        else:
            consecutive = 0
    return False

Complexity Analysis <a name="complexity-analysis"></a>

range is at most 10⁹ (given constraints), so log₂(range) ≤ 30. With n ≤ 10⁵, the algorithm easily fits within typical time limits.

Worked Example <a name="worked-example"></a>

Input
`bloomDay = [1, 10, 3,

The binary search approach efficiently narrows down the possible days by checking the feasibility of making m bouquets on a given day. Because of that, the possible function checks if we can form m bouquets by counting consecutive flowers that have bloomed by the given day. This solution is optimal with a time complexity of O(n log(max_day)), which is efficient for the given constraints Worth keeping that in mind. That's the whole idea..

In the worked example, we found that by day 6, we can form 3 bouquets (each requiring 2 consecutive bloomed flowers). The algorithm correctly identifies 6 as the minimum number of days required, demonstrating its correctness and efficiency. The binary search ensures that we minimize the number of checks

The binary‑search step is only one side of the problem; once the feasible interval has been isolated, the inner predicate tells us whether a particular day is sufficient to assemble the required number of bouquets Small thing, real impact..

Proof of Correctness

Consider the monotonic property of the predicate possible. If a certain day d allows us to create at least m bouquets, then every later day d' ≥ d will also allow it, because more flowers are guaranteed to have bloomed up to d' and therefore cannot reduce the count of consecutive segments of length k. , the minimal feasible day. Now, the loop invariant “all values < left are infeasible and all values ≥ right+1 are feasible” holds initially (left = min(bloomDay), right = max(bloomDay)) and is preserved by the updates when moving right or left. Consequently the set of admissible days forms a suffix of the integer line, and binary search on this ordered set returns the smallest element of that suffix – i.e.When the loop terminates, answer stores the first day that passed the test, which is precisely the desired minimum.

Handling Edge Cases

If the total number of flowers is smaller than m·k, no arrangement can ever succeed. In this situation the routine immediately returns -1 before any binary‑search work is performed, avoiding unnecessary computation.

When m equals zero, the requirement is trivially satisfied on day 0. The algorithm still works because the initial call to possible would never be invoked (the loop would exit with answer = -1), but we can add a guard clause at the top to return 0 directly, saving a few operations.

Large input sizes: With n ≤ 10⁵ and range ≤ 10⁹, the logarithmic factor stays bounded by about thirty iterations, giving a worst‑case runtime well under one second even in compiled languages such as C++ or Java.

Practical Implementation (Python 3)

def min_days(bloom_day, m, k):
    n = len(bloom_day)
    if m * k > n:
        return -1                         # impossible

    lo, hi = min(bloom_day), max(bloom_day)
    ans = -1

    while lo <= hi:
        mid = (lo + hi) // 2
        if enough_bouquets(mid):
            ans = mid
            hi = mid - 1                  # look for a smaller day
        else:
            lo = mid + 1                  # need a later day

    return ans

def enough_bouquets(day):
    bouquets = 0
    streak = 0
    for b in bloom_day:
        if b <= day:
            streak += 1
            if streak == k:
                bouquets += 1
                if bouquets == m:
                    return True
                streak = 0               # start a new segment
        else:
            streak = 0
    return False

The helper enough_bouquets follows exactly the logic described in the pseudocode: it scans the list once, resetting the current streak whenever a flower has not yet bloomed, and counts how many disjoint blocks of size k become fully covered by day mid. As soon as m such blocks are discovered the function returns True.

Full Run‑Through with Sample Data

For the array [1, 10, 3, 5, 8] and parameters m = 2, k = 2:

1. Initial bounds → lo = 1, hi = 10.
2. Mid = 5 → scanning shows two consecutive blooms (3 and 5) after day 5, forming one bouquet; however we still need a second. The remainder yields another block (8), giving exactly two bou