Sponsored
Sponsored
This approach uses binary search to efficiently determine the minimum number of days needed to make the required number of bouquets. By evaluating the feasibility of creating bouquets for a specific day, the search narrows down the smallest number of days possible.
The idea is to perform binary search between the minimum day and the maximum day in the bloomDay array. For each middle day value in the binary search, check if it's possible to make the required number of bouquets within those days. This check involves iterating through the bloomDay array and simulating the bouquet-making process.
If it's possible to make the bouquets on the current day or fewer, adjust the search range towards smaller values; otherwise, increase the range.
Time Complexity: O(n log(max(bloomDay))) where n is the length of the bloomDay array. This is due to binary searching over the day range and checking each day.
Space Complexity: O(1) since no additional data structures proportional to input size are used.
1class Solution {
2 public int minDays(int[] bloomDay, int m, int k) {
3 if (bloomDay.length < m * k) return -1;
4 int low = Integer.MAX_VALUE, high = 0;
5 for (int day : bloomDay) {
6 low = Math.min(low, day);
7 high = Math.max(high, day);
8 }
9 while (low < high) {
10 int mid = low + (high - low) / 2;
11 if (canMakeBouquets(bloomDay, m, k, mid)) {
12 high = mid;
13 } else {
14 low = mid + 1;
15 }
16 }
17 return low;
18 }
19 private boolean canMakeBouquets(int[] bloomDay, int m, int k, int days) {
20 int bouquets = 0, flowers = 0;
21 for (int bloom : bloomDay) {
22 if (bloom <= days) {
23 flowers++;
24 if (flowers == k) {
25 bouquets++;
26 flowers = 0;
27 }
28 } else {
29 flowers = 0;
30 }
31 }
32 return bouquets >= m;
33 }
34}In this Java solution, two functions are used: 'minDays' for binary search and 'canMakeBouquets' as a helper for condition checking. The low and high bounds are initialized based on bloomDay's minimum and maximum values.
A more straightforward but less optimal approach is to simulate each day sequentially and check whether that day allows the creation of the necessary bouquets. This simulation checks for the day on each flower to see if the flower is usable and forms bouquets if possible. This approach refines checking for the earliest feasible day without having an initial constraint of possible day ranges.
Time Complexity: O(n log(max(bloomDay))) as it checks each day incrementally
Space Complexity: O(1)
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5class Solution {
public:
int minDays(vector<int>& bloomDay, int m, int k) {
if (bloomDay.size() < m * k) return -1;
int low = *min_element(bloomDay.begin(), bloomDay.end());
int high = *max_element(bloomDay.begin(), bloomDay.end());
while (low < high) {
int mid = low + (high - low) / 2;
if (canMakeBouquets(bloomDay, m, k, mid)) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
}
private:
bool canMakeBouquets(const vector<int>& bloomDay, int m, int k, int days) {
int bouquets = 0, flowers = 0;
for (int bloom : bloomDay) {
if (bloom <= days) {
flowers++;
if (flowers == k) {
bouquets++;
flowers = 0;
}
} else {
flowers = 0;
}
}
return bouquets >= m;
}
};This C++ solution uses a greedy day-progressive approach by checking feasibility per day and forming bouquets incrementally. It continues this day sequence until meeting the bouquet requirement or reaching day limit.