Minimum Days to Make M Bouquets Binary Search Optimal Solution

Problem Statement❯

You are given an array bloomDay[] where bloomDay[i] represents the day on which the i-th flower will bloom. Your task is to determine the minimum number of days required to make m bouquets, where each bouquet requires k adjacent bloomed flowers.

You can only use a flower if it has bloomed on or before the day you're checking.
You must use exactly k adjacent flowers to make each bouquet.

If it's not possible to make m bouquets, return -1.

Examples❯

Bloom Day Array	m	k	Output	Description
[1, 10, 3, 10, 2]	3	1	3	On day 3, flowers at indices 0, 2, and 4 are bloomed. 3 bouquets possible.
[1, 10, 3, 10, 2]	3	2	-1	Not enough adjacent flowers to form 3 bouquets of 2 flowers.
[7, 7, 7, 7, 12, 7, 7]	2	3	12	Day 12 is the earliest when two bouquets of 3 adjacent flowers can be made.
[1000000000, 1000000000]	1	1	1000000000	Only one flower needed, take the earliest available.
[1, 10, 2, 9, 3, 8]	2	2	9	Day 9 gives two pairs of adjacent bloomed flowers: (2,3) and (4,5)
[1]	1	1	1	One flower, one bouquet needed — return 1.
[1]	2	1	-1	Only one flower, but two bouquets required — not possible.
[]	1	1	-1	Empty array — can't make any bouquets.

Visualization Player

Solution❯

Understanding the Problem

We are given an array of integers where each element represents the day a flower will bloom. Our task is to make m bouquets, each consisting of exactly k adjacent bloomed flowers. A flower can only be used on or after the day it blooms.

The main question is: What is the minimum number of days needed to make m such bouquets?

Step-by-Step Solution with Example

Step 1: Think About a Single Day

Let’s say we choose a day, like day 7. On this day, only flowers that bloom on or before day 7 can be used. We scan the array and try to form bouquets using only these bloomed flowers. We can only form a bouquet if we find k adjacent bloomed flowers.

Step 2: Try to Simulate It

Let’s take an example:

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

This means we need to make 1 bouquet using 2 adjacent bloomed flowers. On day 3, the bloom status is:

Day 1 → bloomed (1 ≤ 3)
Day 10 → not bloomed (10 > 3)
Day 3 → bloomed (3 ≤ 3)
Day 10 → not bloomed
Day 2 → bloomed (2 ≤ 3)

The bloomed flowers are at index 0, 2, and 4. None of them are adjacent, so we cannot form any bouquet on day 3. Try day 10 — now all flowers are bloomed, and we can form a bouquet with [3, 10] or [10, 2]. So day 10 works. We try to find the minimum such day.

Step 3: Use Binary Search to Optimize

Since trying all days linearly is slow, we use binary search on days from the minimum to the maximum bloom value.

At each mid-point day, we check if it's possible to make m bouquets. If it is, we try a smaller day. If it’s not, we try a bigger day. This helps us zero in on the minimum valid day efficiently.

Step 4: Bouquet Formation Check Logic

While scanning, we count how many adjacent bloomed flowers we have. If a flower is bloomed on or before the current day, we increase the count. If not, we reset the count to 0. Every time the count reaches k, we form a bouquet and reset the count.

Edge Cases

Not Enough Flowers: If m × k is greater than the total number of flowers, it's impossible to form the required bouquets. We should return -1 immediately.
All Flowers Bloom Late: Even if all flowers bloom on high days (like day 1000), binary search will still find the answer quickly.
Empty Array: If the array is empty, we cannot form any bouquet. Return -1.
Exactly Enough Flowers: If the array has exactly m × k flowers, we must use every flower — and they must be arranged in proper adjacent groups. This is a tight case to test our adjacency logic.

Finally

We solved this problem using a binary search approach, which significantly improves performance over a brute force solution. The key insights were:

Understanding how to simulate bouquet formation on a specific day
Applying binary search on the range of days to minimize the answer
Carefully handling edge cases, especially when adjacency is required

The time complexity is O(n × log(max bloom day)), where n is the number of flowers. This makes the solution both fast and scalable.

Algorithm Steps❯

Set low = minimum bloom day, high = maximum bloom day.
Perform binary search while low ≤ high.
Set mid = (low + high) / 2.
Check if it’s possible to make m bouquets in mid days using a helper function:

Traverse bloom days. Count consecutive bloomed roses (i.e., arr[i] ≤ mid).
Every time you collect k adjacent, increment bouquet count and reset count.
If bouquet count ≥ m, return true.

If possible, store mid as answer and move high = mid - 1.
Else move low = mid + 1.

Code

Java

Python

JavaScript

C++

Kotlin

Swift

Php

public class Bouquets {
  public static boolean canMakeBouquets(int[] bloomDay, int m, int k, int day) {
    int bouquets = 0, flowers = 0;
    for (int b : bloomDay) {
      if (b <= day) {
        flowers++;
        if (flowers == k) {
          bouquets++;
          flowers = 0;
        }
      } else {
        flowers = 0;  // Reset if bloom not ready
      }
    }
    return bouquets >= m;
  }

  public static int minDays(int[] bloomDay, int m, int k) {
    if ((long)m * k > bloomDay.length) return -1;
    int low = Integer.MAX_VALUE, high = Integer.MIN_VALUE;
    for (int day : bloomDay) {
      low = Math.min(low, day);
      high = Math.max(high, day);
    }
    int ans = -1;
    while (low <= high) {
      int mid = low + (high - low) / 2;
      if (canMakeBouquets(bloomDay, m, k, mid)) {
        ans = mid;
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
    return ans;
  }

  public static void main(String[] args) {
    int[] bloom = {1, 10, 3, 10, 2};
    int m = 3, k = 1;
    System.out.println("Minimum Days: " + minDays(bloom, m, k));
  }
}

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(n)	In the best case, the first binary search guess gives a valid answer after a single bouquet check.
Average Case	O(n log(max_day - min_day))	Binary search runs in log(max_day - min_day) steps and each step checks the full array to count bouquets.
Worst Case	O(n log(max_day - min_day))	Binary search iterates across the entire range of possible days, checking all n roses each time.

Space Complexity❯

O(1)

Explanation: Only a few variables are used; no extra space is needed apart from input.

⬅ Previous TopicKoko Eating Bananas

Next Topic ⮕Find the Smallest Divisor Given a Threshold

Comments

Loading comments...