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

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

✓ Binary Search on Answer

⏱️ Time: O(n × log(max_bloom_day)) Space: O(1)

Instead of checking every day linearly, use binary search on the answer space (days). For each candidate day, check if it's possible to make m bouquets, then adjust search range accordingly.

Brute Force

⏱️ Time: O(n × max_bloom_day) Space: O(1)

For each day from 1 to the maximum bloom day, simulate which flowers have bloomed and count how many valid bouquets can be made with k adjacent bloomed flowers.

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;
    
    // Parse array [1,10,3,10,2]
    char* p = line;
    while (*p && *p != '[') p++; // Find opening bracket
    if (*p == '[') p++; // Skip opening bracket
    
    while (*p && *p != ']') {
        // Skip whitespace and commas
        while (*p == ' ' || *p == ',') p++;
        if (*p == ']' || *p == '\0') break;
        
        // Parse number
        char* endptr;
        bloomDay[n++] = (int)strtol(p, &endptr, 10);
        p = endptr;
    }
    
    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

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables for binary search bounds and counting

✓ Linear Space

89.3K 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

Minimum Number of Days to Make m Bouquets - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search on Answer — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler