Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Minimum Number of Days to Make m Bouquets

MEDIUMProblemSolveExternal Links

Description

You are given an integer array bloomDay of length n, an integer m, and an integer k.

You want to make m bouquets. To make a single bouquet, you need exactly k adjacent flowers that have already bloomed.

The garden has n flowers, and the i-th flower blooms on day bloomDay[i]. Once a flower blooms, it stays bloomed and can be used in exactly one bouquet.

Return the minimum number of days you need to wait so that you can make m bouquets from the garden. If it is impossible to make m bouquets, return -1.

Examples

Example 1

Input: bloomDay = [1, 10, 3, 10, 2], m = 3, k = 1

Output: 3

Explanation: We need 3 bouquets, each containing 1 adjacent flower.

  • After day 1: [x, _, _, _, _] — only flower 0 has bloomed → 1 bouquet possible.
  • After day 2: [x, _, _, _, x] — flowers 0 and 4 bloomed → 2 bouquets possible.
  • After day 3: [x, _, x, _, x] — flowers 0, 2, and 4 bloomed → 3 bouquets possible.

Since k = 1, each bloomed flower alone forms a bouquet. By day 3 we have 3 bouquets, so the answer is 3.

Example 2

Input: bloomDay = [1, 10, 3, 10, 2], m = 3, k = 2

Output: -1

Explanation: We need 3 bouquets, each with 2 adjacent flowers. That requires a total of 3 × 2 = 6 flowers, but there are only 5 flowers in the garden. It is impossible to form 3 bouquets, so we return -1.

Example 3

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

Output: 12

Explanation: We need 2 bouquets, each with 3 adjacent flowers.

  • After day 7: [x, x, x, x, _, x, x] — flowers 0–3 and 5–6 bloomed. We can take flowers 0–2 for one bouquet. Flowers 5–6 only give 2 consecutive bloomed flowers, which is less than k = 3, so we cannot form a second bouquet.
  • After day 12: [x, x, x, x, x, x, x] — all flowers bloomed. We can make bouquets from flowers 0–2 and flowers 3–5 (or many other combinations). The answer is 12.

Constraints

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

Editorial

Brute Force

Intuition

The most straightforward idea is to simulate each possible day and check whether we can form m bouquets on that day.

Think of it like waiting at the garden gate every morning. Each day you walk through the row of flowers, counting consecutive bloomed flowers. Whenever you count k in a row, you have one bouquet. You reset and keep counting. If you reach m bouquets, that day is a valid answer.

The earliest valid day is the answer. We try every day starting from the smallest bloom day up to the largest bloom day. The first day where we can form m bouquets is our result.

To check a single day, we scan through bloomDay left to right. For each flower, if it has bloomed by that day (i.e., bloomDay[i] <= day), we increment a consecutive counter. When the counter reaches k, we have one bouquet — we reset the counter and increment our bouquet count. If the flower has not bloomed, we reset the counter to 0 because the adjacency is broken.

Step-by-Step Explanation

Let's trace through with bloomDay = [7, 7, 7, 7, 12, 7, 7], m = 2, k = 3.

The unique bloom days sorted are [7, 12]. We try each day in order.

Step 1: Try day = 7.

  • Flower 0: bloomDay[0] = 7 ≤ 7 → bloomed. consecutive = 1.
  • Flower 1: bloomDay[1] = 7 ≤ 7 → bloomed. consecutive = 2.
  • Flower 2: bloomDay[2] = 7 ≤ 7 → bloomed. consecutive = 3 = k → bouquets = 1, reset consecutive = 0.
  • Flower 3: bloomDay[3] = 7 ≤ 7 → bloomed. consecutive = 1.
  • Flower 4: bloomDay[4] = 12 > 7 → NOT bloomed. consecutive = 0.
  • Flower 5: bloomDay[5] = 7 ≤ 7 → bloomed. consecutive = 1.
  • Flower 6: bloomDay[6] = 7 ≤ 7 → bloomed. consecutive = 2.
  • End: bouquets = 1 < m = 2. Day 7 is NOT sufficient.

Step 2: Try day = 12.

  • Flower 0: 7 ≤ 12 → bloomed. consecutive = 1.
  • Flower 1: 7 ≤ 12 → bloomed. consecutive = 2.
  • Flower 2: 7 ≤ 12 → bloomed. consecutive = 3 = k → bouquets = 1, reset consecutive = 0.
  • Flower 3: 7 ≤ 12 → bloomed. consecutive = 1.
  • Flower 4: 12 ≤ 12 → bloomed. consecutive = 2.
  • Flower 5: 7 ≤ 12 → bloomed. consecutive = 3 = k → bouquets = 2, reset consecutive = 0.
  • Flower 6: 7 ≤ 12 → bloomed. consecutive = 1.
  • End: bouquets = 2 ≥ m = 2. Day 12 IS sufficient!

Result: The minimum day is 12.

Brute Force — Checking Each Day — Watch how we scan the flower array for each candidate day, counting consecutive bloomed flowers to form bouquets.

Algorithm

  1. If m * k > n, return -1 (impossible — not enough flowers).
  2. Collect all unique bloom days and sort them.
  3. For each candidate day (from smallest to largest):
    a. Scan the bloomDay array left to right.
    b. Maintain a consecutive counter: increment when bloomDay[i] <= day, reset to 0 otherwise.
    c. When consecutive reaches k, increment bouquets and reset consecutive to 0.
    d. If bouquets >= m, return this day.
  4. Return -1 (should not reach here if impossible check was correct).

Code

#include <vector>
#include <algorithm>
#include <set>
using namespace std;

class Solution {
public:
    int minDays(vector<int>& bloomDay, int m, int k) {
        int n = bloomDay.size();
        // Impossible check: need m*k flowers total
        if ((long long)m * k > n) return -1;
        
        // Collect unique days and sort
        set<int> daySet(bloomDay.begin(), bloomDay.end());
        
        for (int day : daySet) {
            int bouquets = 0, consecutive = 0;
            for (int i = 0; i < n; i++) {
                if (bloomDay[i] <= day) {
                    consecutive++;
                    if (consecutive == k) {
                        bouquets++;
                        consecutive = 0;
                    }
                } else {
                    consecutive = 0;
                }
            }
            if (bouquets >= m) return day;
        }
        
        return -1;
    }
};
class Solution:
    def minDays(self, bloomDay: list[int], m: int, k: int) -> int:
        n = len(bloomDay)
        # Impossible check
        if m * k > n:
            return -1
        
        # Collect unique days and sort
        unique_days = sorted(set(bloomDay))
        
        for day in unique_days:
            bouquets = 0
            consecutive = 0
            for bloom in bloomDay:
                if bloom <= day:
                    consecutive += 1
                    if consecutive == k:
                        bouquets += 1
                        consecutive = 0
                else:
                    consecutive = 0
            if bouquets >= m:
                return day
        
        return -1
import java.util.*;

class Solution {
    public int minDays(int[] bloomDay, int m, int k) {
        int n = bloomDay.length;
        // Impossible check
        if ((long) m * k > n) return -1;
        
        // Collect unique days and sort
        TreeSet<Integer> daySet = new TreeSet<>();
        for (int d : bloomDay) daySet.add(d);
        
        for (int day : daySet) {
            int bouquets = 0, consecutive = 0;
            for (int i = 0; i < n; i++) {
                if (bloomDay[i] <= day) {
                    consecutive++;
                    if (consecutive == k) {
                        bouquets++;
                        consecutive = 0;
                    }
                } else {
                    consecutive = 0;
                }
            }
            if (bouquets >= m) return day;
        }
        
        return -1;
    }
}

Complexity Analysis

Time Complexity: O(n × d)

Where n is the length of bloomDay and d is the number of unique bloom days (up to n). For each of the d candidate days, we scan the entire array of n flowers. In the worst case, d = n, giving O(n²).

Space Complexity: O(d)

We store the unique days in a sorted set, which can hold up to n elements. So space is O(n) in the worst case.

Why This Approach Is Not Efficient

The brute force tries every unique bloom day one by one, from smallest to largest. In the worst case there are up to n = 10^5 unique days, and for each day we scan the entire array of n flowers. This gives O(n²) time — up to 10^10 operations — which is far too slow for the given constraints.

The key observation is: if we can make m bouquets by day d, then we can also make m bouquets on any day d' > d (because more flowers will have bloomed). This monotonic property means the answer satisfies a classic binary search pattern:

  • Days below the answer: cannot form m bouquets (too few blooms).
  • Days at or above the answer: can form m bouquets.

Instead of trying every day linearly, we can binary search over the range of days. Each binary search probe calls the same O(n) feasibility check, but we only do O(log(max_day)) probes instead of O(n). Since max_day ≤ 10^9, we need at most ~30 probes.

Optimal Approach - Binary Search on Answer

Intuition

The insight that unlocks this problem is noticing the monotonic relationship between the number of waiting days and the number of bouquets we can form.

Imagine a timeline from day 1 to the latest bloom day. On the far left (day 1), very few flowers have bloomed, so we likely cannot form m bouquets. On the far right (the maximum bloom day), every flower is bloomed, so if it is possible at all, we can certainly form m bouquets.

As the day increases, more flowers bloom, and the number of achievable bouquets can only stay the same or increase — it never decreases. This monotonic behavior is exactly the pattern binary search exploits.

We define a helper function canMake(day) that checks whether, on a given day, we can form at least m bouquets. This function scans the bloomDay array once (O(n) time), counting consecutive bloomed flowers.

Then we binary search over the range [min(bloomDay), max(bloomDay)] for the smallest day where canMake(day) returns true.

This reduces our search from O(n) candidate days to O(log(max - min)) probes, and each probe costs O(n). Total time becomes O(n × log(max_bloom_day)), which is extremely efficient.

Step-by-Step Explanation

Let's trace through with bloomDay = [1, 10, 3, 10, 2], m = 3, k = 1.

First, check impossibility: m × k = 3 × 1 = 3 ≤ 5 = n, so it might be possible.

Search range: low = min(bloomDay) = 1, high = max(bloomDay) = 10.

Step 1: mid = (1 + 10) / 2 = 5.

  • canMake(5): scan bloomDay.
    • Flower 0: 1 ≤ 5 → consecutive = 1 = k → bouquets = 1, reset.
    • Flower 1: 10 > 5 → consecutive = 0.
    • Flower 2: 3 ≤ 5 → consecutive = 1 = k → bouquets = 2, reset.
    • Flower 3: 10 > 5 → consecutive = 0.
    • Flower 4: 2 ≤ 5 → consecutive = 1 = k → bouquets = 3, reset.
    • bouquets = 3 ≥ m = 3 → TRUE.
  • Day 5 works. But is there a smaller day? Search left: high = 5.

Step 2: mid = (1 + 5) / 2 = 3.

  • canMake(3): scan bloomDay.
    • Flower 0: 1 ≤ 3 → consecutive = 1 = k → bouquets = 1, reset.
    • Flower 1: 10 > 3 → consecutive = 0.
    • Flower 2: 3 ≤ 3 → consecutive = 1 = k → bouquets = 2, reset.
    • Flower 3: 10 > 3 → consecutive = 0.
    • Flower 4: 2 ≤ 3 → consecutive = 1 = k → bouquets = 3, reset.
    • bouquets = 3 ≥ 3 → TRUE.
  • Day 3 works. Search left: high = 3.

Step 3: mid = (1 + 3) / 2 = 2.

  • canMake(2): scan bloomDay.
    • Flower 0: 1 ≤ 2 → consecutive = 1 = k → bouquets = 1, reset.
    • Flower 1: 10 > 2 → consecutive = 0.
    • Flower 2: 3 > 2 → consecutive = 0.
    • Flower 3: 10 > 2 → consecutive = 0.
    • Flower 4: 2 ≤ 2 → consecutive = 1 = k → bouquets = 2, reset.
    • bouquets = 2 < 3 → FALSE.
  • Day 2 doesn't work. Search right: low = 3.

Step 4: low = 3, high = 3. low == high, so the answer is 3.

Result: The minimum number of days is 3.

Binary Search on Days — Finding Minimum Wait — Watch how binary search narrows the range of possible days. For each candidate day, we scan the array to check if enough bouquets can be formed.

Algorithm

  1. If m * k > n, return -1 (not enough flowers).
  2. Set low = min(bloomDay), high = max(bloomDay).
  3. While low < high:
    a. Compute mid = low + (high - low) / 2.
    b. Call canMake(mid): scan bloomDay, count consecutive bloomed flowers. Each time the consecutive count reaches k, increment bouquet count and reset.
    c. If canMake(mid) returns true (bouquets ≥ m), set high = mid.
    d. Otherwise, set low = mid + 1.
  4. Return low.

Helper — canMake(day):

  1. Initialize bouquets = 0, consecutive = 0.
  2. For each flower i from 0 to n-1:
    • If bloomDay[i] <= day, increment consecutive. If consecutive == k, increment bouquets, reset consecutive = 0.
    • Else, reset consecutive = 0.
  3. Return bouquets >= m.

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int minDays(vector<int>& bloomDay, int m, int k) {
        int n = bloomDay.size();
        if ((long long)m * k > n) return -1;
        
        int low = *min_element(bloomDay.begin(), bloomDay.end());
        int high = *max_element(bloomDay.begin(), bloomDay.end());
        
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (canMake(bloomDay, mid, m, k)) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        
        return low;
    }
    
private:
    bool canMake(vector<int>& bloomDay, int day, int m, int k) {
        int bouquets = 0, consecutive = 0;
        for (int i = 0; i < bloomDay.size(); i++) {
            if (bloomDay[i] <= day) {
                consecutive++;
                if (consecutive == k) {
                    bouquets++;
                    consecutive = 0;
                }
            } else {
                consecutive = 0;
            }
        }
        return bouquets >= m;
    }
};
class Solution:
    def minDays(self, bloomDay: list[int], m: int, k: int) -> int:
        n = len(bloomDay)
        if m * k > n:
            return -1
        
        def canMake(day: int) -> bool:
            bouquets = 0
            consecutive = 0
            for bloom in bloomDay:
                if bloom <= day:
                    consecutive += 1
                    if consecutive == k:
                        bouquets += 1
                        consecutive = 0
                else:
                    consecutive = 0
            return bouquets >= m
        
        low = min(bloomDay)
        high = max(bloomDay)
        
        while low < high:
            mid = low + (high - low) // 2
            if canMake(mid):
                high = mid
            else:
                low = mid + 1
        
        return low
class Solution {
    public int minDays(int[] bloomDay, int m, int k) {
        int n = bloomDay.length;
        if ((long) m * k > n) return -1;
        
        int low = Integer.MAX_VALUE, high = Integer.MIN_VALUE;
        for (int d : bloomDay) {
            low = Math.min(low, d);
            high = Math.max(high, d);
        }
        
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (canMake(bloomDay, mid, m, k)) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        
        return low;
    }
    
    private boolean canMake(int[] bloomDay, int day, int m, int k) {
        int bouquets = 0, consecutive = 0;
        for (int bloom : bloomDay) {
            if (bloom <= day) {
                consecutive++;
                if (consecutive == k) {
                    bouquets++;
                    consecutive = 0;
                }
            } else {
                consecutive = 0;
            }
        }
        return bouquets >= m;
    }
}

Complexity Analysis

Time Complexity: O(n × log(max_bloom_day))

The binary search operates over the range [min(bloomDay), max(bloomDay)]. The size of this range can be up to 10^9, so binary search performs at most log₂(10^9) ≈ 30 iterations. Each iteration runs the canMake function which scans all n flowers in O(n) time. Total: O(n × 30) = O(n × log(max_bloom_day)).

For n = 10^5, this is about 3 × 10^6 operations — well within time limits.

Space Complexity: O(1)

We only use a constant number of variables (low, high, mid, bouquets, consecutive). No additional data structures are allocated. The input array is read but not modified.