Problem Statement
You are given an integer array bloomDay, where each element represents the day on which a specific flower bloom. You are also given two integers m and k.
m: the number of bouquets you need to make.k: the number of adjacent flowers required to make one bouquet.
The task is to find the minimum number of days required to make exactly m bouquets from the flowers in the bloomDay array. Each bouquet requires exactly k adjacent flowers that have all bloomed by a particular day.
If it is impossible to make m bouquets, return -1.
Examples
Example 1:
Input: bloomDay = [1, 10, 3, 10, 2], m = 3, k = 1
Output: 3
Explanation:
- You need 3 bouquets, each with 1 flower.
- By day 3, there are 3 flowers bloomed (on days 1, 3, and 2)
- You can make 3 bouquets by picking these flowers.
- The answer is 3.Example 2:
Input: bloomDay = [7, 7, 7, 7, 11, 12, 7], m = 2, k = 3
Output: 12
Explanation:
- You need 2 bouquets with 3 flowers each.
- By day 12, the first 4 flowers and the last 3 flowers would have already bloomed.
- So, we can easily make 2 bouquets, one with the first 3 and
another with the last 3 flowers.Example 3:
Input: bloomDay = [1, 10, 3, 10, 2], m = 3, k = 2
Output: -1
Explanation:
- You need to make 3 bouquets of 2 flowers each, so we need atleast 5 flowers.
- But we are given only 5 flowers, so we cannot make the bouquets.Different Approaches
1️⃣ Brute Force Approach
Intuition:
The very straightforward approach is to check all possible answers from range min to max linearly, where min is the minimum element of the array and max is the maximum element of the array. Each number in the range shows the number of days. The minimum number of days for which at least m bouquet can be made each containing k rose will be our final answer.
Dry Run:
+-----+-----+-----+-----+-----+-----+-----+-----+
bloomDay = | 7 | 7 | 7 | 7 | 13 | 11 | 12 | 7 |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6 7
m = 2
k = 3Day 7:
Min of array Max of array
| |
+-----+-----+-----+-----+-----+-----+-----+
search Space = | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
+-----+-----+-----+-----+-----+-----+-----+
^
|
day
count = 0
numberOfBouquets = 0
i = 0
+-----+-----+-----+-----+-----+-----+-----+-----+
bloomDay = | 7 | 7 | 7 | 7 | 13 | 11 | 12 | 7 |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6 7
^
|
i
Since nums[i] <= day
7 <= 7
True
Increment count
count = count + 1
= 0 + 1
= 1
i = 1
count = 1
numberOfBouquets = 0
+-----+-----+-----+-----+-----+-----+-----+-----+
bloomDay = | 7 | 7 | 7 | 7 | 13 | 11 | 12 | 7 |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6 7
^
|
i
Since nums[i] <= day
7 <= 7
True
Increment count
count = count + 1
= 1 + 1
= 2
i = 2
count = 2
numberOfBouquets = 0
+-----+-----+-----+-----+-----+-----+-----+-----+
bloomDay = | 7 | 7 | 7 | 7 | 13 | 11 | 12 | 7 |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6 7
^
|
i
Since nums[i] <= day
7 <= 7
True
Increment count
count = count + 1
= 2 + 1
= 3
i = 3
count = 3
numberOfBouquets = 0
+-----+-----+-----+-----+-----+-----+-----+-----+
bloomDay = | 7 | 7 | 7 | 7 | 13 | 11 | 12 | 7 |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6 7
^
|
i
Since nums[i] <= day
7 <= 7
True
Increment count
count = count + 1
= 3 + 1
= 4
i = 4
count = 4
numberOfBouquets = 0
+-----+-----+-----+-----+-----+-----+-----+-----+
bloomDay = | 7 | 7 | 7 | 7 | 13 | 11 | 12 | 7 |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6 7
^
|
i
Since nums[i] <= day
13 <= 7
False
check how many bouqeuts can be formed from continuous bloomed flower's
count
numberOfBouquets = numberOfBouquets + (count / k)
= 0 + (4 / 3)
= 1
Set count to 0
count = 0
i = 5
count = 0
numberOfBouquets = 1
+-----+-----+-----+-----+-----+-----+-----+-----+
bloomDay = | 7 | 7 | 7 | 7 | 13 | 11 | 12 | 7 |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6 7
^
|
i
Since nums[i] <= day
11 <= 7
False
check how many bouqeuts can be formed from continuous bloomed flower's
count
numberOfBouquets = numberOfBouquets + (count / k)
= 1 + (0 / 3)
= 1
Set count to 0
count = 0
i = 6
count = 0
numberOfBouquets = 1
+-----+-----+-----+-----+-----+-----+-----+-----+
bloomDay = | 7 | 7 | 7 | 7 | 13 | 11 | 12 | 7 |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6 7
^
|
i
Since nums[i] <= day
12 <= 7
False
check how many bouqeuts can be formed from continuous bloomed flower's
count
numberOfBouquets = numberOfBouquets + (count / k)
= 1 + (0 / 3)
= 1
Set count to 0
count = 0
i = 7
count = 0
numberOfBouquets = 1
+-----+-----+-----+-----+-----+-----+-----+-----+
bloomDay = | 7 | 7 | 7 | 7 | 13 | 11 | 12 | 7 |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6 7
^
|
i
Since nums[i] <= day
7 <= 7
True
Incrmeent count by one
count = count = 1
= 0 + 1
= 1
check how many bouqeuts can be formed from continuous bloomed flower's
count
numberOfBouquets = numberOfBouquets + (count / k)
= 1 + (0 / 3)
= 1
Set count to 0
count = 0
Internal Loop Termination:
i = 8
count = 1
numberOfBouquets = 1
+-----+-----+-----+-----+-----+-----+-----+-----+
bloomDay = | 7 | 7 | 7 | 7 | 13 | 11 | 12 | 7 |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6 7
^
|
i
Since i has crossed the array bounds the loop will terminate.
After loop completion check how many bouqeuts can be formed
from the count.
check how many bouqeuts can be formed from continuous bloomed flower's
count
numberOfBouquets = numberOfBouquets + (count / k)
= 1 + (1 / 3)
= 1
So for the day 7, we can only form 1 bouquet of 3 flower which is continuous.
Which is less than the m (2), so we do the same for the next day,
day 8.
..
..
..
Atlast we would find out that day on day 12,
we can make 2 buquets of 3 continuous flowers.
Thus we have to return minimum number of days to make at least
2 bouquets each containing 3 flowers.Code:
#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
/* Function to check if it's possible to make
m bouquets with k flowers each on day */
bool possible(vector<int> &nums, int day, int m, int k) {
int n = nums.size();
// Count of flowers bloomed
int cnt = 0;
// Count of bouquets formed
int noOfB = 0;
// Count number of bouquets that can be formed
for (int i = 0; i < n; i++) {
if (nums[i] <= day) {
// Increment flower count
cnt++;
} else {
/* Calculate number of bouquets
formed with flowers <= day */
noOfB += (cnt / k);
// Reset flower count
cnt = 0;
}
}
// Add remaining flowers as a bouquet
noOfB += (cnt / k);
/* Return true if enough
bouquets can be formed */
return noOfB >= m;
}
public:
/* Function to find the earliest day to
make m bouquets of k flowers each */
int roseGarden(int n, vector<int> nums, int k, int m) {
/* Calculate the minimum
number of flowers required*/
long long val = m * 1ll * k * 1ll;
/* Impossible case: not enough
flowers to make m bouquets*/
if (val > n) return -1;
/* Find maximum and minimum
bloom days in the array */
int mini = INT_MAX, maxi = INT_MIN;
for (int i = 0; i < n; i++) {
mini = min(mini, nums[i]);
maxi = max(maxi, nums[i]);
}
/* Linear search to find the
earliest day to make m bouquets */
for (int i = mini; i <= maxi; i++) {
if (possible(nums, i, m, k))
return i;
}
// Return-1 if no such day exists
return -1;
}
};
int main() {
vector<int> arr = {7, 7, 7, 7, 13, 11, 12, 7};
int n = arr.size();
// Number of flowers per bouquet
int k = 3;
// Number of bouquets needed
int m = 2;
// Create an instance of the Solution class
Solution sol;
int ans = sol.roseGarden(n, arr, k, m);
if (ans == -1) {
cout << "We cannot make m bouquets.\n";
} else {
cout << "We can make bouquets on day " << ans << "\n";
}
return 0;
}
Complexity Analysis:
- Time Complexity:
O((max-min + 1)*N), wheremaxis the maximum element of the array,minis the minimum element of the array,Nis the size of the array.- The outer loop to check answers in the range of
[min, max]. - The inner loop traverse the entire array, which results in
O(N).
- The outer loop to check answers in the range of
- Space Complexity:
O(1)
2️⃣ Binary Search
Intuition:
The idea is to use binary search algorithm as the search range [min, max] is sorted, where, min is the earliest and max is the latest day for a rose to bloom. So, it it's feasible to make m bouquets on day mid. Else, eliminate the left half to find a higher range of days.
- All the flowers will be bloomed on the max element's day, which would be our high.
Edge Case:
If the product k*m is greater than the size of the array, then it is impossible to make bouquet, in that case return -1.
Code:
#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
/* Function to check if it's possible to make
m bouquets with k flowers each on day */
bool possible(vector<int> &nums, int day, int m, int k) {
int n = nums.size();
// Count of flowers bloomed
int cnt = 0;
// Count of bouquets formed
int noOfB = 0;
// Count number of bouquets that can be formed
for (int i = 0; i < n; i++) {
if (nums[i] <= day) {
// Increment flower count
cnt++;
} else {
/* Calculate number of bouquets
formed with flowers <= day */
noOfB += (cnt / k);
// Reset flower count
cnt = 0;
}
}
// Add remaining flowers as a bouquet
noOfB += (cnt / k);
/* Return true if enough
bouquets can be formed */
return noOfB >= m;
}
public:
/* Function to find the earliest day to
make m bouquets of k flowers each */
int roseGarden(int n, vector<int> nums, int k, int m) {
/* Calculate the minimum
number of flowers required*/
long long val = m * 1ll * k * 1ll;
/* Impossible case: not enough
flowers to make m bouquets*/
if (val > n) return -1;
/* Find maximum and minimum
bloom days in the array */
int mini = INT_MAX, maxi = INT_MIN;
for (int i = 0; i < n; i++) {
mini = min(mini, nums[i]);
maxi = max(maxi, nums[i]);
}
/* Binary search to find the
earliest day to make m bouquets */
int left = mini, right = maxi, ans = -1;
while (left <= right) {
// Calculate the middle day
int mid = left + (right - left) / 2;
/* Check if it's possible to
make m bouquets on day mid */
if (possible(nums, mid, m, k)) {
// Update the answer to mid
ans = mid;
// Try for a smaller day
right = mid - 1;
} else {
left = mid + 1;
}
}
/* Return the earliest day or
-1 if no such day exists */
return ans;
}
};
int main() {
vector<int> arr = {7, 7, 7, 7, 13, 11, 12, 7};
int n = arr.size();
// Number of flowers per bouquet
int k = 3;
// Number of bouquets needed
int m = 2;
// Create an instance of the Solution class
Solution sol;
int ans = sol.roseGarden(n, arr, k, m);
if (ans == -1) {
cout << "We cannot make m bouquets.\n";
} else {
cout << "We can make bouquets on day " << ans << "\n";
}
return 0;
}
Complexity Analysis:
- Time Complexity:
O(log(max-min + 1)*N), wheremaxis the maximum element of the array,minis the minimum element of the array,Nis size of the array.- The outer loop is to check answers that are in the range of [min, max].
- The inner loop is to traverse the entire array, which results in
O(N).
- Space Complexity:
O(1).