Minimum number of Days to make m Bouquets

Problem Link

minimum-number-of-days-to-make-m-bouquets

Problem Statement

You are given:

• An integer array bloomDay, where bloomDay[i] denotes the day the i-th flower blooms.

• Two integers m and k.

Your task is to make m bouquets, each consisting of k adjacent flowers.

A flower can only be used once, and only after it has bloomed (i.e., on or after bloomDay[i]).

Return the minimum number of days required to make all m bouquets. If it's not possible, return -1.

Examples

Example 1

Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
Output: 3
Explanation:
We need 3 bouquets with 1 adjacent flower each. By Day 3, 3 flowers have bloomed: [1,3,2].

Example 2

Input: bloomDay = [1,10,3,10,2], m = 3, k = 2
Output: -1
Explanation:
We need 3 bouquets with 2 flowers each → 6 flowers total. Only 5 flowers available → Not possible.

Example 3

Input: bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
Output: 12
Explanation:
Need 2 bouquets with 3 adjacent flowers. By Day 7, not enough adjacent groups. Day 12 makes it possible.

Constraints

• 1 <= bloomDay.length <= 10^5

• 1 <= bloomDay[i] <= 10^9

• 1 <= m <= 10^6

• 1 <= k <= bloomDay.length

Intuition

This is a "Search on Answer" type of problem. We are to find the minimum day d such that it becomes possible to form m bouquets of k adjacent flowers using flowers that have bloomed on or before day d.

If for a particular day d it is possible to form the bouquets, it may also be possible for greater values of d. This makes the function monotonic, allowing the use of binary search.

Approach

1. Base Case:

   • If m * k > n (where n is length of array), return -1 immediately (not enough flowers).

2. Binary Search Range:

   • Start: min bloomDay

   • End: max bloomDay

3. Binary Search:

   • For each mid day, check if it’s possible to make m bouquets using a helper function.

4. Possible Check:

   • Traverse the array, keep a count of consecutive bloomed flowers (<= day)

   • Every time you get k consecutive bloomed flowers, increment bouquet count.

   • Reset counter when you hit an unbloomed flower.

5. Final Answer:

   • The smallest day for which making m bouquets is possible.

Java Code

class Solution {
    public int minDays(int[] bloomDay, int m, int k) {
        long required = (long) m * k;
        int n = bloomDay.length;
        if (required > n) return -1;

        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int day : bloomDay) {
            min = Math.min(min, day);
            max = Math.max(max, day);
        }

        int low = min, high = max;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (canMakeBouquets(bloomDay, mid, m, k)) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return low;
    }

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

Time and Space Complexity

• Time Complexity:

  • O(n * log(maxDay))
n for each feasibility check, log(maxDay) for binary search

• Space Complexity:

  • O(1)
    Only variables, no extra data structures

Dry Run

Input:

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

Process:

• Binary search on days: range = [1, 10]

• Try mid = 5 → check if 3 bouquets possible with flowers bloomed by Day 5:

  • Blooms on day ≤ 5: [1, 3, 2] → 3 flowers → 3 bouquets (each of 1 flower)

• Feasible → try lower days → result = 3

Output:

3

Conclusion

This is a classic binary search problem where we search the minimum valid time needed to meet a condition. The challenge lies in checking the condition efficiently using greedy logic (counting adjacent bloomed flowers).

It reinforces important concepts:

• Binary search on answer space

• Greedy feasibility checking

• Efficient handling of large inputs under strict constraints