Log inSign up
mediumleetcodeNot Started

Minimum Number of Days to Make m Bouquets

Given an integer array bloomDay, an integer m and an integer k, return the minimum number of days you need to wait to be able to make m bouquets from adjacent flowers of size k, or -1 if impossible.

Binary Search
Solve on leetcode
Lesson

Problem Statement

You are given an integer array bloomDay, an integer m and an integer k.\n\nYou want to make m bouquets. To make a bouquet, you need to use k adjacent flowers from the garden.\n\nThe garden consists of n flowers, the i-th flower will bloom in the bloomDay[i] and then can be used in exactly one bouquet.\n\nReturn the minimum number of days you need to wait to be able to make m bouquets from the garden. If it is impossible to make m bouquets return -1.

Example 1 · Example 1: Standard Case:

Input: bloomDay = [1, 10, 3, 10, 2], m = 3, k = 1
Output: 3
Explanation: On day 3, flowers 0, 2, and 4 bloom ([1, _, 3, _, 2]), allowing us to make 3 bouquets of size 1.

Example 2 · Example 2: Impossible Case:

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

Example 3 · Example 3: Adjacent Requirement:

Input: bloomDay = [7, 7, 7, 7, 12, 7, 7], m = 2, k = 3
Output: 12
Explanation: On day 7 we have 4 bloomed flowers on left (1 bouquet) and 2 on right (not enough for second bouquet). On day 12 all bloom, giving 2 bouquets.

Constraints:

  • bloomDay.length == n
  • 1 <= n <= 105
  • 1 <= bloomDay[i] <= 109
  • 1 <= m <= 106
  • 1 <= k <= n

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Formulate greedy contiguous grouping verification in O(n).
  • Apply binary search on answer for day threshold.
  • Handle large integer multiplication overflow (m * k > n).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Optimization problem asking for 'minimum days / threshold'.
  • Requires adjacent/contiguous elements.
  • Monotonic predicate: more days means at least as many bloomed flowers.

Algorithmic Decision Tree:

  • If (long)m * k > n -> return -1.
  • low = min(bloomDay), high = max(bloomDay), ans = -1.
  • While low <= high: mid = low + (high - low) / 2.
  • If canMake(mid, m, k) -> ans = mid, high = mid - 1.
  • Else low = mid + 1.
  • Return ans.

Connected Patterns:

Koko Eating BananasCapacity To Ship Packages Within D DaysMagnetic Force Between Two Balls

1. Linear Day Scan

Intuition

First check (long)m * k > n. Then iterate day d sequentially. For each day, iterate through flowers counting consecutive bloomed flowers. Return first day where bouquets >= m.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: If (long)m * k > bloomDay.length return -1.
  2. Step 2: Loop day from min(bloomDay) to max(bloomDay).
  3. Step 3: Count bouquets formed by counting streaks of flowers with bloomDay[i] <= day.
  4. Step 4: If bouquets >= m, return day.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int minDays(vector<int>& bloomDay, int m, int k) {
10 if ((long long)m * k > bloomDay.size()) return -1;
11 int minD = 1e9, maxD = 0;
12 for (int d : bloomDay) {
13 minD = min(minD, d);
14 maxD = max(maxD, d);
15 }
16 for (int day = minD; day <= maxD; ++day) {
17 int bouquets = 0, count = 0;
18 for (int d : bloomDay) {
19 if (d <= day) {
20 count++;
21 if (count == k) {
22 bouquets++;
23 count = 0;
24 }
25 } else {
26 count = 0;
27 }
28 }
29 if (bouquets >= m) return day;
30 }
31 return -1;
32 }
33};
34
35int main() {
36 // Sample driver execution
37 cout << "Execution completed successfully." << endl;
38 return 0;
39}
40

Time & Space Complexity

  • Time complexity: O(n * (max(bloomDay) - min(bloomDay))) — Can take up to 109 iterations of O(n) work.
  • Space complexity: O(1) — O(1) memory.

2. Unique Sorted Bloom Days Traversal

Intuition

Extract distinct bloom days and sort them. Test only these distinct days linearly instead of every integer day.

When to apply: When there are very few distinct bloom days.

Algorithm

  1. Step 1: Check if (long)m * k > n, return -1 if true.
  2. Step 2: Collect distinct values of bloomDay into a sorted list.
  3. Step 3: Test each unique day sequentially using greedy bouquet counter.
  4. Step 4: Return first valid day.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int minDays(vector<int>& bloomDay, int m, int k) {
10 if ((long long)m * k > bloomDay.size()) return -1;
11 vector<int> uniqueDays = bloomDay;
12 sort(uniqueDays.begin(), uniqueDays.end());
13 uniqueDays.erase(unique(uniqueDays.begin(), uniqueDays.end()), uniqueDays.end());
14
15 for (int day : uniqueDays) {
16 int bouquets = 0, count = 0;
17 for (int d : bloomDay) {
18 if (d <= day) {
19 count++;
20 if (count == k) {
21 bouquets++;
22 count = 0;
23 }
24 } else {
25 count = 0;
26 }
27 }
28 if (bouquets >= m) return day;
29 }
30 return -1;
31 }
32};
33
34int main() {
35 // Sample driver execution
36 cout << "Execution completed successfully." << endl;
37 return 0;
38}
39

Time & Space Complexity

  • Time complexity: O(u * n + n log n) — Where u is the number of unique days (up to n). Takes O(n2) worst case.
  • Space complexity: O(u) — O(u) memory to store unique days.

3. Binary Search on Answer Range

Intuition

Set low = min(bloomDay), high = max(bloomDay). In each step compute mid. Run greedy check: if bouquets >= m, ans = mid and high = mid - 1; else low = mid + 1.

When to apply: Standard optimal solution.

Algorithm

  1. Step 1: If (long)m * k > bloomDay.length return -1.
  2. Step 2: low = min(bloomDay), high = max(bloomDay), ans = -1.
  3. Step 3: While low <= high:
  4. - mid = low + (high - low) / 2.
  5. - count = 0, bouquets = 0.
  6. - For d in bloomDay: if d <= mid { count++; if (count == k) { bouquets++; count = 0; } } else count = 0.
  7. - If bouquets >= m: ans = mid, high = mid - 1.
  8. - Else low = mid + 1.
  9. Step 4: Return ans.

Trace for bloomDay = [1, 10, 3, 10, 2], m = 3, k = 1

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Range [1, 10]
Visual state
Values and pointers at this exact step
pointers
S
Bloomed
Closed
Bloomed
Closed
Bloomed
0
↑ low
1
2
3
4
↑ high
Check / comparison
At day 5, formed 3 bouquets >= m (3) -> Valid day.
Decision / next transition
Record ans = 5, set high = 4.
Why this step matters

Range [1, 10]. mid=5. Bloomed on day 5: [1(Y), 10(N), 3(Y), 10(N), 2(Y)] -> 3 bouquets formed >= 3. Valid day! ans=5. Search left: high = mid - 1 = 4.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int minDays(vector<int>& bloomDay, int m, int k) {
10 if ((long long)m * k > bloomDay.size()) return -1;
11
12 int low = 1e9, high = 0;
13 for (int d : bloomDay) {
14 low = min(low, d);
15 high = max(high, d);
16 }
17
18 int ans = -1;
19 while (low <= high) {
20 int mid = low + (high - low) / 2;
21 int bouquets = 0, count = 0;
22 for (int d : bloomDay) {
23 if (d <= mid) {
24 count++;
25 if (count == k) {
26 bouquets++;
27 count = 0;
28 }
29 } else {
30 count = 0;
31 }
32 }
33 if (bouquets >= m) {
34 ans = mid;
35 high = mid - 1;
36 } else {
37 low = mid + 1;
38 }
39 }
40 return ans;
41 }
42};
43
44int main() {
45 // Sample driver execution
46 cout << "Execution completed successfully." << endl;
47 return 0;
48}
49

Time & Space Complexity

  • Time complexity: O(n * log(max(bloomDay) - min(bloomDay))) — Search range is at most 109, meaning log2(109) ~ 30 iterations. Each iteration scans n elements.
  • Space complexity: O(1) — Operates in-place using O(1) extra variables.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Linear Day ScanO(n * range)O(1)Test every day from min to max.Inspects every single day value.
2.Unique Bloom Days ScanO(u * n)O(u)Test only distinct bloom days.Linear scan through unique days.
3.Binary Search on AnswerOptimalO(n * log(range))O(1)Binary search on monotonic day predicate.None. This is optimal.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • m * k > n -> return -1 immediately.
  • m * k == n -> all flowers must bloom, answer is max(bloomDay).
  • k = 1 -> can pick any m bloomed flowers.
  • All bloom days are identical.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Show how m * k > n check upfront saves computation.
  2. Explain the greedy choice in canMake: taking a bouquet as soon as k contiguous flowers are ready is always optimal.
  3. Emphasize that flowers must be adjacent, so non-bloomed flowers reset the streak.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why must we reset the consecutive flower count when bloomDay[i] > day?

Back to DSA Sheet