Minimum Days to Make M Bouquets

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.

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.

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.

#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;
}

#include <iostream>
#include <vector>
using namespace std;

bool canMakeBouquets(vector<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;
    }
  }
  return bouquets >= m;
}

int minDays(vector<int>& bloomDay, int m, int k) {
  if ((long)m * k > bloomDay.size()) return -1;
  int low = *min_element(bloomDay.begin(), bloomDay.end());
  int high = *max_element(bloomDay.begin(), bloomDay.end());
  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;
}

int main() {
  vector<int> bloom = {1, 10, 3, 10, 2};
  cout << "Minimum Days: " << minDays(bloom, 3, 1) << endl;
  return 0;
}

def can_make_bouquets(bloom_day, m, k, day):
    bouquets = flowers = 0
    for b in bloom_day:
        if b <= day:
            flowers += 1
            if flowers == k:
                bouquets += 1
                flowers = 0
        else:
            flowers = 0
    return bouquets >= m

def min_days(bloom_day, m, k):
    if m * k > len(bloom_day):
        return -1
    low, high = min(bloom_day), max(bloom_day)
    ans = -1
    while low <= high:
        mid = (low + high) // 2
        if can_make_bouquets(bloom_day, m, k, mid):
            ans = mid
            high = mid - 1
        else:
            low = mid + 1
    return ans

bloom = [1, 10, 3, 10, 2]
m, k = 3, 1
print("Minimum Days:", min_days(bloom, m, k))

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;
      }
    }
    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));
  }
}

function canMakeBouquets(bloomDay, m, k, day) {
  let bouquets = 0, flowers = 0;
  for (let b of bloomDay) {
    if (b <= day) {
      flowers++;
      if (flowers === k) {
        bouquets++;
        flowers = 0;
      }
    } else {
      flowers = 0;
    }
  }
  return bouquets >= m;
}

function minDays(bloomDay, m, k) {
  if (m * k > bloomDay.length) return -1;
  let low = Math.min(...bloomDay), high = Math.max(...bloomDay);
  let ans = -1;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (canMakeBouquets(bloomDay, m, k, mid)) {
      ans = mid;
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return ans;
}

const bloom = [1, 10, 3, 10, 2];
console.log("Minimum Days:", minDays(bloom, 3, 1));

package main

import (
  "fmt"
)

func canMakeBouquets(bloomDay []int, m, k, day int) bool {
  bouquets, flowers := 0, 0
  for _, b := range bloomDay {
    if b <= day {
      flowers++
      if flowers == k {
        bouquets++
        flowers = 0
      }
    } else {
      flowers = 0
    }
  }
  return bouquets >= m
}

func minDays(bloomDay []int, m, k int) int {
  if m*k > len(bloomDay) {
    return -1
  }
  low, high := bloomDay[0], bloomDay[0]
  for _, day := range bloomDay {
    if day < low {
      low = day
    }
    if day > high {
      high = day
    }
  }
  ans := -1
  for low <= high {
    mid := (low + high) / 2
    if canMakeBouquets(bloomDay, m, k, mid) {
      ans = mid
      high = mid - 1
    } else {
      low = mid + 1
    }
  }
  return ans
}

func main() {
  bloom := []int{1, 10, 3, 10, 2}
  m, k := 3, 1
  fmt.Println("Minimum Days:", minDays(bloom, m, k))
}

fn can_make_bouquets(bloom_day: &Vec<i32>, m: i32, k: i32, day: i32) -> bool {
    let mut bouquets = 0;
    let mut flowers = 0;
    for &b in bloom_day.iter() {
        if b <= day {
            flowers += 1;
            if flowers == k {
                bouquets += 1;
                flowers = 0;
            }
        } else {
            flowers = 0;
        }
    }
    bouquets >= m
}

fn min_days(bloom_day: Vec<i32>, m: i32, k: i32) -> i32 {
    if m * k > bloom_day.len() as i32 {
        return -1;
    }
    let mut low = *bloom_day.iter().min().unwrap();
    let mut high = *bloom_day.iter().max().unwrap();
    let mut ans = -1;
    while low <= high {
        let mid = (low + high) / 2;
        if can_make_bouquets(&bloom_day, m, k, mid) {
            ans = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    ans
}

fn main() {
    let bloom = vec![1, 10, 3, 10, 2];
    let m = 3;
    let k = 1;
    println!("Minimum Days: {}", min_days(bloom, m, k));
}

fun canMakeBouquets(bloomDay: IntArray, m: Int, k: Int, day: Int): Boolean {
    var bouquets = 0
    var flowers = 0
    for (b in bloomDay) {
        if (b <= day) {
            flowers++
            if (flowers == k) {
                bouquets++
                flowers = 0
            }
        } else {
            flowers = 0
        }
    }
    return bouquets >= m
}

fun minDays(bloomDay: IntArray, m: Int, k: Int): Int {
    if (m.toLong() * k > bloomDay.size) return -1
    var low = bloomDay.minOrNull()!!
    var high = bloomDay.maxOrNull()!!
    var ans = -1
    while (low <= high) {
        val mid = low + (high - low) / 2
        if (canMakeBouquets(bloomDay, m, k, mid)) {
            ans = mid
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return ans
}

fun main() {
    val bloom = intArrayOf(1, 10, 3, 10, 2)
    println("Minimum Days: ${minDays(bloom, 3, 1)}")
}

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

function minDays(bloomDay: number[], m: number, k: number): number {
  if (m * k > bloomDay.length) return -1;
  let low = Math.min(...bloomDay), high = Math.max(...bloomDay);
  let ans = -1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (canMakeBouquets(bloomDay, m, k, mid)) {
      ans = mid;
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return ans;
}

const bloom = [1, 10, 3, 10, 2];
console.log("Minimum Days:", minDays(bloom, 3, 1));

Time complexity

Space complexity

O(1)

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