Binary SearchMediumO(n log(max_day)) time · O(1) space

Min Days to Make M Bouquets

Ramayana — Sita's Garden — The Earliest Day When M Garlands Can Be Woven

कितने दिनों में m माला बनेगी?। न्यूनतमः दिनाङ्कः — जब k क्रमिक पुष्पाः खिलते हों॥

*In how many days can m garlands be made? The minimum day — when k consecutive flowers bloom.*

The Story

Given an array `bloomDay` where `bloomDay[i]` is the day flower i blooms, make m bouquets each needing k consecutive bloomed flowers. Find the minimum number of days, or -1 if impossible.

For `bloomDay=[1,10,3,10,2]`, m=3, k=1: answer=3 (on day 3, flowers 0,2,4 are bloomed; 3 bouquets each of 1 flower).

**Binary Search on Answer:** - Range: [1, max(bloomDay)] - Feasibility for day `d`: count bouquets we can make (consecutive runs of bloomed flowers / k) - Find minimum d such that bouquets ≥ m

```java public int minDays(int[] bloomDay, int m, int k) { if ((long)m * k > bloomDay.length) return -1; int lo=1, hi=1000000000; while (lo < hi) { int mid = (lo+hi)/2; if (canMake(bloomDay, m, k, mid)) hi=mid; else lo=mid+1; } return lo; }

boolean canMake(int[] bd, int m, int k, int day) { int bouquets=0, consecutive=0; for (int d : bd) { if (d <= day) { consecutive++; if (consecutive==k) { bouquets++; consecutive=0; } } else consecutive=0; } return bouquets >= m; } ```

Sita needed exactly m garlands of k consecutive blooms. She binary searched the answer: for each candidate day, she checked if enough consecutive flowers had bloomed.

**`if (long)m*k > n: return -1`** — early exit: even if all n flowers bloom, we can't make m×k flowers if n < m×k.

The Day-by-Day Checker

Try each day from 1 to max. Check feasibility. O(n × max_day).

java

public int minDaysBruteForce(int[] bloomDay, int m, int k) {
    if ((long)m*k > bloomDay.length) return -1;
    int maxDay = 0;
    for (int d : bloomDay) maxDay = Math.max(maxDay, d);
    for (int day = 1; day <= maxDay; day++) {
        int bouquets=0, cons=0;
        for (int bd : bloomDay) {
            if (bd<=day) { cons++; if(cons==k){bouquets++;cons=0;} } else cons=0;
        }
        if (bouquets >= m) return day;
    }
    return -1;
}

Sita's Binary-Search-on-Day Wisdom

Binary search on day ∈ [1, max_bloomDay]. For each day: count bouquets from consecutive runs of length k. If ≥m: feasible (hi=mid). Else infeasible (lo=mid+1).

java

public int minDays(int[] bloomDay, int m, int k) {
    if ((long) m * k > bloomDay.length) return -1;
    int lo = 1, hi = (int) 1e9;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canMake(bloomDay, m, k, mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

private boolean canMake(int[] bloomDay, int m, int k, int day) {
    int bouquets = 0, consecutive = 0;
    for (int bd : bloomDay) {
        if (bd <= day) {
            consecutive++;
            if (consecutive == k) { bouquets++; consecutive = 0; }
        } else {
            consecutive = 0;
        }
    }
    return bouquets >= m;
}

Step-by-Step Walkthrough

[1], m=1, k=1
m*k=1 ≤ 1 ✓
lo=1,hi=1e9. mid=5e8. canMake(bloomDay[0]=1≤5e8 → bouquets=1≥1) → hi=5e8
...converges to lo=1 ✅

Deep Insight

**Same template as bs-11:** Binary search on answer + feasibility check. The feasibility function (canMake) is monotone: more days → more flowers bloom → easier to make bouquets.

**Consecutive flower counting:** The canMake function counts runs of consecutive bloomed flowers. When consecutive reaches k, a bouquet is made and consecutive resets. A non-bloomed flower breaks any current run.

**hi initialization:** Setting hi=1e9 (max possible bloom day) is safe even without computing max(bloomDay). Slightly less efficient but simpler.

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n × max_day)	O(1)	Check every day
Optimal	O(n log max_day)	O(1)	Binary search + O(n) feasibility check per step

Pattern Recognition

✅ Binary search on answer (day)
✅ Feasibility: count bouquets from consecutive k-blooms
✅ Early exit: m*k > n → return -1
✅ Same template as Koko, Aggressive Cows, Ship Packages

**LeetCode Trigger Phrases:**
→ "minimum days" to make bouquets
→ Consecutive count + threshold condition

Bhagavad Gita 2.28

अव्यक्तादीनि भूतानि व्यक्तमध्यानि भारत।

All created beings are unmanifest before their birth and after their death. Only during the interval of life are they manifest.

Connection: Each flower has its moment of blooming — unmanifest before its day, fully present on and after it. The algorithm searches for the earliest day when enough of these manifestations align consecutively to weave complete garlands. Like the Gita's teaching on the cycle of manifestation, the binary search finds the minimum threshold of time required for sufficient consecutive blossoming to produce the required beauty.