Minimum Days to Make M Bouquets Binary Search Optimal Solution

Arrays - Binary Search

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

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.

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❯

  1. Set low = minimum bloom day, high = maximum bloom day.
  2. Perform binary search while low ≤ high.
  3. Set mid = (low + high) / 2.
  4. 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.
  5. If possible, store mid as answer and move high = mid - 1.
  6. Else move low = mid + 1.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
TS
#include <stdio.h>

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

int minDays(int bloomDay[], int n, int m, int k) {
  if ((long)m * k > n) return -1;
  int low = 1e9, high = 0, ans = -1;
  for (int i = 0; i < n; i++) {
    if (bloomDay[i] < low) low = bloomDay[i];
    if (bloomDay[i] > high) high = bloomDay[i];
  }
  while (low <= high) {
    int mid = low + (high - low) / 2;
    if (canMakeBouquets(bloomDay, n, m, k, mid)) {
      ans = mid;
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return ans;
}

int main() {
  int bloom[] = {1, 10, 3, 10, 2};
  int m = 3, k = 1;
  printf("Minimum Days: %d\n", minDays(bloom, 5, m, k));
  return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n)In the best case, the first binary search guess gives a valid answer after a single bouquet check.
Average CaseO(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 CaseO(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.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...