Given a garden with n different flowers and an array arr[], where ith flower will bloom after arr[i] days. To create one bouquet, you need to pick k adjacent flowers from the garden. You want to make a total of m bouquets. Find the minimum number of days you need to wait to make m bouquets from the garden. If it's impossible to create m bouquets, return -1.
Examples:
Input: m = 3, k = 2, arr[] = [3, 4, 2, 7, 13, 8, 5]
Output: 8
Explanation: We need 3 bouquets and each bouquet should have 2 flowers. After day 8: [x, x, x, x, _, x, x], we can make first bouquet from the first 2 flowers, second bouquet from the next 2 flowers and the third bouquet from the last 2 flowers.Input: m = 2, k = 3, arr[] = [5, 5, 5, 5, 10, 5, 5]
Output: 10
Explanation: We need 2 bouquets and each bouquet should have 3 flowers, After day 5: [x, x, x, x, _, x, x], we can make one bouquet of the first three flowers that bloomed, but cannot make another bouquet. After day 10: [x, x, x, x, x, x, x], Now we can make two bouquets, taking 3 adjacent flowers in one bouquet.Input: m = 3, k = 2, arr[] = [1, 10, 3, 10, 2]
Output: -1
Explanation: As 3 bouquets each having 2 flowers are needed, that means we need 6 flowers. But there are only 5 flowers so it is impossible to get the needed bouquets therefore -1 will be returned.
Try it on GfG Practice
Table of Content
[Naive Approach] Using Linear Search - O(n × max(arr)) Time and O(1) Space
The idea is to iterate over all possible days d starting from 0 to largest bloom day. To find whether it is possible to make m bouquets in d days, we traverse the array arr[] and check if there is at least m contiguous subarrays of size k such that each subarray has element <= d.
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
// function to check if the given number of days is
// valid for creating bouquets
bool check(vector<int> &arr, int k, int m, int days) {
int bouquets = 0;
int cnt = 0;
// iterate through the bloom days of the flowers
for (int i = 0; i < arr.size(); i++) {
if (arr[i] <= days) {
cnt += 1;
}
else {
// if the current bloom day count is greater
// than days, update bouquets and reset count
bouquets += cnt / k;
cnt = 0;
}
}
bouquets += cnt / k;
// check if current bouquets are greater than or
// equal to the desired number of bouquets (m)
return bouquets >= m;
}
int minDaysBloom(vector<int> &arr, int k, int m) {
int maxDays = *max_element(arr.begin(), arr.end());
for (int d = 0; d <= maxDays; d++) {
if (check(arr, k, m, d))
return d;
}
return -1;
}
int main() {
vector<int> arr = {5, 5, 5, 5, 10, 5, 5};
int k = 3, m = 2;
cout << minDaysBloom(arr, k, m);
return 0;
}
import java.util.Arrays;
class GfG {
// function to check if the given number of days is
// valid for creating bouquets
static boolean check(int[] arr, int k,
int m, int days){
int bouquets = 0;
int cnt = 0;
// iterate through the bloom days of the flowers
for (int i = 0; i < arr.length; i++) {
if (arr[i] <= days) {
cnt += 1;
}
else {
// if the current bloom day count is greater
// than days, update bouquets and reset count
bouquets += cnt / k;
cnt = 0;
}
}
bouquets += cnt / k;
// check if current bouquets are greater than or
// equal to the desired number of bouquets (m)
return bouquets >= m;
}
static int minDaysBloom(int[] arr, int k, int m) {
int maxDays = Arrays.stream(arr).max().getAsInt();
for (int d = 0; d <= maxDays; d++) {
if (check(arr, k, m, d))
return d;
}
return -1;
}
public static void main(String[] args) {
int[] arr = {5, 5, 5, 5, 10, 5, 5};
int k = 3, m = 2;
System.out.println(minDaysBloom(arr, k, m));
}
}
# function to check if the given number of days is
# valid for creating bouquets
def check(arr, k, m, days):
bouquets = 0
cnt = 0
# iterate through the bloom days of the flowers
for i in range(len(arr)):
if arr[i] <= days:
cnt += 1
else:
# if the current bloom day count is greater
# than days, update bouquets and reset count
bouquets += cnt // k
cnt = 0
bouquets += cnt // k
# check if current bouquets are greater than or
# equal to the desired number of bouquets (m)
return bouquets >= m
def minDaysBloom(arr, k, m):
maxDays = max(arr)
for d in range(maxDays + 1):
if check(arr, k, m, d):
return d
return -1
if __name__ == "__main__":
arr = [5, 5, 5, 5, 10, 5, 5]
k = 3
m = 2
print(minDaysBloom(arr, k, m))
using System;
using System.Linq;
class GfG {
// Function to check if the given number of days is
// valid for creating bouquets
static bool check(int[] arr, int k, int m, int days) {
int bouquets = 0;
int cnt = 0;
// Iterate through the bloom days of the flowers
for (int i = 0; i < arr.Length; i++) {
if (arr[i] <= days) {
cnt += 1;
}
else {
// If the current bloom day count is greater
// than days, update bouquets and reset count
bouquets += cnt / k;
cnt = 0;
}
}
bouquets += cnt / k;
// Check if current bouquets are greater than or
// equal to the desired number of bouquets (m)
return bouquets >= m;
}
static int minDaysBloom(int[] arr, int k, int m) {
int maxDays = arr.Max();
for (int d = 0; d <= maxDays; d++) {
if (check(arr, k, m, d))
return d;
}
return -1;
}
static void Main() {
int[] arr = { 5, 5, 5, 5, 10, 5, 5 };
int k = 3, m = 2;
Console.WriteLine(minDaysBloom(arr, k, m));
}
}
// function to check if the given number of days is
// valid for creating bouquets
function check(arr, k, m, days) {
let bouquets = 0;
let cnt = 0;
// iterate through the bloom days of the flowers
for (let i = 0; i < arr.length; i++) {
if (arr[i] <= days) {
cnt += 1;
} else {
// if the current bloom day count is greater
// than days, update bouquets and reset count
bouquets += Math.floor(cnt / k);
cnt = 0;
}
}
bouquets += Math.floor(cnt / k);
// check if current bouquets are greater than or
// equal to the desired number of bouquets (m)
return bouquets >= m;
}
function minDaysBloom(arr, k, m) {
const maxDays = Math.max(...arr);
for (let d = 0; d <= maxDays; d++) {
if (check(arr, k, m, d))
return d;
}
return -1;
}
// Driver Code
const arr = [5, 5, 5, 5, 10, 5, 5];
const k = 3;
const m = 2;
console.log(minDaysBloom(arr, k, m));
Output
10
[Expected Approach] Using Binary Search
The idea is to use Binary search on answer. Our search space would be 0 to largest bloom day of flower, which represent the range in which minimum number of required days will lie. Now, calculate mid and check if mid days is possible to make m bouquet, such that k bloomed adjacent flowers can be selected to make a bouquet.
=> If possible then update the result with mid value and move towards lesser values in search space by updating high to mid - 1.
=> Otherwise, move towards larger values in search space by updating low to mid + 1.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// function to check if the given number of
// days is valid for creating bouquets
bool check(vector<int>& arr, int k, int m,
int days) {
int bouquets = 0;
int cnt = 0;
// iterate through the bloom
// days of the flowers
for (int i = 0; i < arr.size(); i++) {
if (arr[i] <= days) {
cnt += 1;
}
else {
// if the current bloom day count
// is greater than days, update
// the bouquets and reset count
bouquets += cnt / k;
cnt = 0;
}
}
bouquets += cnt / k;
// check if current bouquets are greater
// than or equal to the desired
// number of bouquets (m)
return bouquets >= m;
}
// function to find the minimum number
// of days needed to create m bouquets
int minDaysBloom(vector<int>& arr, int k, int m) {
int lo = 0;
int hi = *max_element(arr.begin(), arr.end());
int res = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (check(arr, k, m, mid)) {
// if the current mid is
// valid, update the result
// and adjust the search range
res = mid;
hi = mid - 1;
}
else {
// if the current mid is
// not valid, adjust the
// search range
lo = mid + 1;
}
}
return res;
}
int main() {
vector<int> arr = {5, 5, 5, 5, 10, 5, 5};
int k = 3, m = 2;
cout << minDaysBloom(arr, k, m);
return 0;
}
import java.util.Arrays;
class GfG {
static boolean check(int[] arr, int k,
int m, int days) {
int bouquets = 0;
int cnt = 0;
// iterate through the bloom
// days of the flowers
for (int i = 0; i < arr.length; i++) {
if (arr[i] <= days) {
cnt += 1;
} else {
// if the current bloom day count
// is greater than days, update
// the bouquets and reset count
bouquets += cnt / k;
cnt = 0;
}
}
bouquets += cnt / k;
// check if current bouquets are greater
// than or equal to the desired
// number of bouquets (m)
return bouquets >= m;
}
static int minDaysBloom(int[] arr, int k, int m) {
int lo = 0;
int hi = Arrays.stream(arr).max().getAsInt();
int res = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (check(arr, k, m, mid)) {
// if the current mid is valid update
// the result and adjust the search range
res = mid;
hi = mid - 1;
}
else {
// if the current mid is not valid
// adjust the search range
lo = mid + 1;
}
}
return res;
}
public static void main(String[] args) {
int[] arr = {5, 5, 5, 5, 10, 5, 5};
int k = 3, m = 2;
System.out.println(minDaysBloom(arr, k, m));
}
}
def check(arr, k, m, days):
bouquets = 0
cnt = 0
# iterate through the bloom
# days of the flowers
for flower in arr:
if flower <= days:
cnt += 1
else:
# if the current bloom day count
# is greater than days, update
# the bouquets and reset count
bouquets += cnt // k
cnt = 0
bouquets += cnt // k
# check if current bouquets are greater
# than or equal to the desired
# number of bouquets (m)
return bouquets >= m
def minDaysBloom(arr, k, m):
lo = 0
hi = max(arr)
res = -1
while lo <= hi:
mid = (lo + hi) // 2
if check(arr, k, m, mid):
# if the current mid is valid update the result
# and adjust the search range
res = mid
hi = mid - 1
else:
# if the current mid is not valid
# adjust the search range
lo = mid + 1
return res
if __name__ == "__main__":
arr = [5, 5, 5, 5, 10, 5, 5]
k = 3
m = 2
print(minDaysBloom(arr, k, m))
using System;
using System.Linq;
class GfG {
static bool check(int[] arr, int k,
int m, int days) {
int bouquets = 0;
int cnt = 0;
// Iterate through the bloom
// days of the flowers
for (int i = 0; i < arr.Length; i++) {
if (arr[i] <= days) {
cnt += 1;
} else {
// If the current bloom day count
// is greater than days, update
// the bouquets and reset count
bouquets += cnt / k;
cnt = 0;
}
}
bouquets += cnt / k;
// Check if current bouquets are greater
// than or equal to the desired
// number of bouquets (m)
return bouquets >= m;
}
static int minDaysBloom(int[] arr, int k, int m) {
int lo = 0;
int hi = arr.Max();
int res = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (check(arr, k, m, mid)) {
// if the current mid is valid, update the
// result and adjust the search range
res = mid;
hi = mid - 1;
} else {
// if the current mid is not valid
// adjust the search range
lo = mid + 1;
}
}
return res;
}
static void Main() {
int[] arr = {5, 5, 5, 5, 10, 5, 5};
int k = 3;
int m = 2;
Console.WriteLine(minDaysBloom(arr, k, m));
}
}
function check(arr, k, m, days) {
let bouquets = 0;
let cnt = 0;
// iterate through the bloom
// days of the flowers
for (let i = 0; i < arr.length; i++) {
if (arr[i] <= days) {
cnt += 1;
}
else {
// if the current bloom day count
// is greater than days, update
// the bouquets and reset count
bouquets += Math.floor(cnt / k);
cnt = 0;
}
}
bouquets += Math.floor(cnt / k);
// check if current bouquets are greater
// than or equal to the desired
// number of bouquets (m)
return bouquets >= m;
}
function minDaysBloom(arr, k, m) {
let lo = 0;
let hi = Math.max(...arr);
let res = -1;
while (lo <= hi) {
let mid = Math.floor((lo + hi) / 2);
if (check(arr, k, m, mid)) {
// if the current mid is valid update the
// result and adjust the search range
res = mid;
hi = mid - 1;
} else {
// if the current mid is not valid
// adjust the search range
lo = mid + 1;
}
}
return res;
}
// Driver Code
let arr = [5, 5, 5, 5, 10, 5, 5];
let k = 3;
let m = 2;
console.log(minDaysBloom(arr, k, m));
Output
10
Time complexity: O(n × log(maxDays)), where n is the number of elements in the array, and maxDays is the maximum possible number of days for a flower to bloom.
Auxiliary Space: O(1)