Minimum Days to Make M Bouquets

56k
0

You are given an integer array bloomDay, an integer m and an integer k. You want to make m bouquets. To make a bouquet, you need to use k adjacent flowers from the garden. The garden consists of n flowers, the ith flower will bloom in the bloomDay[i] and then can be used in exactly one bouquet. Return the minimum number of days you need to wait to be able to make m bouquets from the garden. If it is impossible to make m bouquets return -1.

Example 1

Input: bloomDay = [1, 10, 3, 10, 2], m = 3, k = 1

Output: 3

Explanation: We need 3 bouquets, each containing 1 flower (3 x 1 = 3 flowers total).

  • On Day 1, the flower at index 0 blooms, we can make 1 bouquet.

  • On Day 2, the flower at index 4 blooms, we can make 2 bouquets.

  • On Day 3, the flower at index 2 blooms, we can make 3 bouquets.

  • Therefore, the minimum time needed is 3 days.

Example 2

Input: bloomDay = [1, 10, 3, 10, 2], m = 3, k = 2

Output: -1

Explanation: We need 3 bouquets, each requiring 2 adjacent flowers. This means we need a total of 3 x 2 = 6 flowers. Since there are only 5 flowers in the garden, it is impossible to make the required bouquets.

Brute Force Approach

The most direct idea is to try every possible day. For a chosen day, every flower with bloomDay[i] <= day is available. Consecutive available flowers can be counted. Whenever the count reaches k, one bouquet is formed and the consecutive count is reset. If a flower has not bloomed yet, the current adjacent chain breaks. That matters because a bouquet cannot skip over an unbloomed flower. This approach follows the problem statement very closely, but it may check many days one by one.

Algorithm

  • First, check whether m x k is greater than the total number of flowers. This is done because if the required number of flowers does not exist, no number of days can make the answer possible.

  • Find the smallest and largest bloom day. The answer cannot be before the first bloom day and does not need to be after the last bloom day.

  • Try every day from the smallest bloom day to the largest bloom day. For each day, check whether enough bouquets can be formed.

  • While checking a day, count adjacent bloomed flowers. If a flower has not bloomed by that day, reset the count because the adjacent chain is broken.

  • As soon as a day can make at least m bouquets, return that day because days are checked in increasing order.

Key Points

  • m x k > total number of flowers means the answer is immediately -1.

Dry Run

Minimum Days to Make M Bouquets Brute Dry Run

Minimum Days to Make M Bouquets Brute Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*
Checks if at least m bouquets can be made
by the given day using adjacent flowers.
*/
bool canMakeBouquets(vector<int>& bloomDay, int day, int m, int k) {
// This counts bloomed flowers that are adjacent so far.
int consecutive = 0;
// This counts how many complete bouquets are already formed.
int bouquets = 0;
for (int bloom : bloomDay) {
// This flower can be used because it has bloomed by the chosen day.
if (bloom <= day) {
consecutive++;
// k adjacent bloomed flowers complete one bouquet.
if (consecutive == k) {
bouquets++;
// Reset because these flowers are already used
// in the bouquet that was just made.
consecutive = 0;
}
} else {
// An unbloomed flower breaks the adjacent group,
// so the current consecutive count must restart.
consecutive = 0;
}
}
// The chosen day works only if enough bouquets were formed.
return bouquets >= m;
}
/*
Returns the minimum day needed to make
m bouquets from adjacent bloomed flowers.
*/
int minDays(vector<int>& bloomDay, int m, int k) {
int n = (int)bloomDay.size();
// If total required flowers are more than available flowers,
// making all bouquets is impossible.
if ((long long)m * k > n) {
return -1;
}
// The answer cannot be smaller than the earliest bloom day.
int minDay = *min_element(bloomDay.begin(), bloomDay.end());
// The answer never needs to go beyond the latest bloom day.
int maxDay = *max_element(bloomDay.begin(), bloomDay.end());
for (int day = minDay; day <= maxDay; day++) {
// The first working day is the minimum because
// days are checked in increasing order.
if (canMakeBouquets(bloomDay, day, m, k)) {
return day;
}
}
return -1;
}
};
// Driver code starts
int main() {
vector<int> bloomDay = {1, 10, 3, 10, 2};
int m = 3;
int k = 1;
Solution obj;
cout << obj.minDays(bloomDay, m, k) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N x Range), where Range = max(bloomDay) - min(bloomDay) + 1 and N is the length of array, because every possible day may scan the full array.

Space Complexity: O(1), because constant space is used.

Optimal Approach

The important observation is monotonic. If it is possible to make m bouquets on some day x, then it will also be possible on every day after x. More flowers may bloom later, but already bloomed flowers do not disappear.

That means the answer has this shape: not possible, not possible, not possible, possible, possible, possible

Whenever a problem has this kind of yes-or-no pattern over a range of values, binary search on the answer becomes useful.

Here, the answer is a day. So instead of checking every day one by one, check the middle day:

  • If bouquets can be made by the middle day, try to find an even smaller day.

  • If bouquets cannot be made by the middle day, search later days.

The same helper check is used, but binary search reduces the number of days tested.

Algorithm

  • First, check whether m x k is greater than the number of flowers. This avoids unnecessary work because it is impossible to make enough bouquets without enough flowers.

  • Set low to the minimum bloom day and high to the maximum bloom day. The minimum valid answer must lie inside this range.

  • Pick the middle day and check whether at least m bouquets can be formed by that day. This check scans the array and counts adjacent bloomed flowers.

  • If the middle day works, store it as the current answer and move high to mid - 1. This is done because a smaller day may also work, and the problem asks for the minimum day.

  • If the middle day does not work, move low to mid + 1. This is done because earlier days will have even fewer bloomed flowers, so they cannot work either.

  • Continue until the search range ends, then return the stored answer.

Dry Run

Minimum Days to Make Optimal Dry Run

Minimum Days to Make Optimal Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*
Checks if at least m bouquets can be made
by the given day using adjacent flowers.
*/
bool canMakeBouquets(vector<int>& bloomDay, int day, int m, int k) {
// This counts bloomed flowers that are adjacent so far.
int consecutive = 0;
// This counts how many complete bouquets are already formed.
int bouquets = 0;
for (int bloom : bloomDay) {
// This flower can be used because it has bloomed by the chosen day.
if (bloom <= day) {
consecutive++;
// k adjacent bloomed flowers complete one bouquet.
if (consecutive == k) {
bouquets++;
// Reset because these flowers are already used
// in the bouquet that was just made.
consecutive = 0;
}
} else {
// An unbloomed flower breaks the adjacent group,
// so the current consecutive count must restart.
consecutive = 0;
}
}
// The chosen day works only if enough bouquets were formed.
return bouquets >= m;
}
/*
Returns the minimum day needed to make
m bouquets using binary search on days.
*/
int minDays(vector<int>& bloomDay, int m, int k) {
int n = (int)bloomDay.size();
// If total required flowers are more than available flowers,
// making all bouquets is impossible.
if ((long long)m * k > n) {
return -1;
}
// The answer cannot be smaller than the earliest bloom day.
int low = *min_element(bloomDay.begin(), bloomDay.end());
// The answer never needs to go beyond the latest bloom day.
int high = *max_element(bloomDay.begin(), bloomDay.end());
// This stores the best working day found so far.
int answer = -1;
while (low <= high) {
// mid is the day currently being tested.
int mid = low + (high - low) / 2;
// If mid works, save it and search for a smaller valid day.
if (canMakeBouquets(bloomDay, mid, m, k)) {
answer = mid;
high = mid - 1;
} else {
// If mid does not work, earlier days cannot work either.
low = mid + 1;
}
}
return answer;
}
};
// Driver code starts
int main() {
vector<int> bloomDay = {1, 10, 3, 10, 2};
int m = 3;
int k = 1;
Solution obj;
cout << obj.minDays(bloomDay, m, k) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N x log2(Range)), where Range = max(bloomDay) - min(bloomDay) + 1 and N is the length of array, because each binary search on the range check scans the full array.

Space Complexity: O(1) because constant space is used.

Interview follow-up Questions

This guarantees mathematical feasibility. If you need 3 bouquets of 2 flowers each, you need 6 flowers. If the garden only has 5 flowers, no amount of waiting will magically grow a 6th flower. This early check saves unnecessary computation.

Two PointerSortingMathsBinary SearchArrays

Read Similar Blogs

Arrays

Row wise traversal

Given a matrix with N rows and M columns, print all elements row by row from left to right. Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1 2 3 , then sec...

61.7k
Arrays

Main Diagonal Print

Given a matrix with N rows and M columns, print all elements present on the main diagonal. Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: 1 5 9 Explanation: Main diagonal cell...

67.1k
Arrays

Search Element in Matrix

Given a matrix with N rows and M columns and a target value X , search for X in the matrix. Return the position of the first occurrence of X as {row, col} . Return {-1, -1} when the target value is...

98.4k
Comments0