Minimum Number of Days to Make m Bouquets

Minimum Number of Days to Make m Bouquets - Problem

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

You want to make m bouquets. To make a bouquet, you need to use k adjacent flowers from the garden.

The garden consists of n flowers, the i^th flower will bloom in the bloomDay[i] and then can be used in exactly one bouquet.

Return 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.

Input & Output

Example 1 — Basic Case

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

› Output: 3

💡 Note: By day 3, flowers at indices 0, 2, and 4 have bloomed (bloom days 1, 3, 2). Each bouquet needs k=1 adjacent flower, so we can make 3 bouquets from positions [0], [2], [4].

Example 2 — Adjacent Required

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

› Output: -1

💡 Note: We need 2 bouquets with k=2 adjacent flowers each (total 4 flowers). But we only have 5 flowers total, and they never form 2 groups of 2 adjacent bloomed flowers simultaneously.

Example 3 — Later Day Needed

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

› Output: 12

💡 Note: By day 7, all flowers except index 4 have bloomed. We need 2 groups of 3 adjacent flowers. Only by day 12 when all flowers bloom can we make groups [0,1,2] and [4,5,6].

Constraints

1 ≤ bloomDay.length ≤ 10⁵
1 ≤ bloomDay[i] ≤ 10⁹
1 ≤ m, k ≤ bloomDay.length

Visualization

Tap to expand

Understanding the Visualization

Input

Array of bloom days, m bouquets needed, k adjacent flowers per bouquet

Process

Find minimum day when m groups of k adjacent bloomed flowers exist

Output

Minimum number of days to wait, or -1 if impossible

Key Takeaway

🎯 Key Insight: Binary search on the answer space (days) is much more efficient than checking every day sequentially

Asked in

f Facebook 35 G Google 28 a Amazon 22

The key insight is to use binary search on the answer space (days) rather than checking each day linearly. We binary search on the number of days and for each candidate day, check if we can make m bouquets by counting consecutive groups of k bloomed flowers. Best approach is Binary Search on Answer with Time: O(n × log(max_bloom_day)), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search on Answer	O(n × log(max_bloom_day))	O(1)	Binary search on the number of days to find minimum
Brute Force	O(n × max_bloom_day)	O(1)	Check every day from 1 to maximum bloom day

Binary Search on Answer — Algorithm Steps

Step 1: Set search range from min to max bloom day
Step 2: For middle day, check if m bouquets possible
Step 3: If possible, search left half for smaller day
Step 4: If not possible, search right half for larger day

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial Range

Search between min and max bloom days

Test Middle

Check if mid day allows m bouquets

Narrow Range

Eliminate half the search space

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int canMakeBouquets(int* bloomDay, int n, int day, int m, int k) {
    int bouquets = 0;
    int consecutive = 0;
    
    for (int i = 0; i < n; i++) {
        if (bloomDay[i] <= day) {
            consecutive++;
            if (consecutive == k) {
                bouquets++;
                consecutive = 0;
            }
        } else {
            consecutive = 0;
        }
    }
    
    return bouquets >= m;
}

int solution(int* bloomDay, int n, int m, int k) {
    if (n < m * k) return -1;
    
    int left = bloomDay[0], right = bloomDay[0];
    for (int i = 0; i < n; i++) {
        if (bloomDay[i] < left) left = bloomDay[i];
        if (bloomDay[i] > right) right = bloomDay[i];
    }
    
    int result = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (canMakeBouquets(bloomDay, n, mid, m, k)) {
            result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int bloomDay[1000];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token) {
        bloomDay[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int m, k;
    scanf("%d", &m);
    scanf("%d", &k);
    
    printf("%d\n", solution(bloomDay, n, m, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × log(max_bloom_day))

Binary search takes O(log(max_bloom_day)) iterations, each iteration scans n flowers

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra variables for binary search bounds and counting

✓ Linear Space

89.2K Views

Medium Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search on Answer — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler