Leetcode 1482: Minimum Number of Days to Make m Bouquets
You are given an integer array bloomDay, an integer m, and an integer k. Your goal is to form m bouquets using exactly k adjacent flowers. Each flower blooms on a particular day. Determine the minimum number of days required to form m bouquets, or return -1 if it is impossible.
Problem
Approach
Steps
Complexity
Input: The input consists of an integer array bloomDay, and integers m and k.
Example: [2, 5, 3, 4, 1], m = 3, k = 2
Constraints:
• 1 <= bloomDay.length <= 10^5
• 1 <= bloomDay[i] <= 10^9
• 1 <= m <= 10^6
• 1 <= k <= bloomDay.length
Output: The output should be a single integer representing the minimum number of days required to form m bouquets, or -1 if it is impossible.
Example: 4
Constraints:
• The result is guaranteed to be a valid integer.
Goal: The goal is to determine the minimum number of days to wait in order to be able to make m bouquets.
Steps:
• Perform a binary search on the number of days, starting with the lowest possible day and checking if it's feasible to form m bouquets in that time.
• To check if m bouquets can be formed by a certain day, count the number of adjacent flowers that bloom by that day, and see if you can form m bouquets with k flowers each.
Goal: The problem requires the use of a binary search algorithm to efficiently find the solution, ensuring that the solution can handle the large input sizes.
Steps:
• 1 <= bloomDay.length <= 10^5
• 1 <= bloomDay[i] <= 10^9
• 1 <= m <= 10^6
• 1 <= k <= bloomDay.length
Assumptions:
• The flowers bloom on specific days and can only be used once for a bouquet.
• The flowers must be adjacent to form a bouquet.
• Input: [2, 5, 3, 4, 1], m = 3, k = 2
• Explanation: After 4 days, we can make 3 bouquets of 2 adjacent flowers. The solution works by checking if it's possible to make the bouquets by each day in the binary search process.
Approach: The solution involves performing a binary search on the number of days. For each day, we check if it's possible to make the required bouquets by counting the number of adjacent blooming flowers.
Observations:
• The problem requires determining if it is possible to make m bouquets by checking different days in a binary search approach.
• Binary search helps us efficiently find the minimum number of days, reducing the number of checks.
Steps:
• Start with a binary search over the possible number of days.
• For each mid-point day in the search, check if m bouquets can be made using the function isValid.
• If m bouquets can be made, try searching for a smaller number of days, otherwise search for a larger number of days.
Empty Inputs:
• If the array is empty, return -1 as no bouquets can be made.
Large Inputs:
• Ensure the solution handles arrays with up to 10^5 elements efficiently.
Special Values:
• If m is 0 or k is greater than the total number of flowers, return -1.
Constraints:
• The algorithm must be efficient enough to handle the upper limit of input size.
int isValid(vector<int> &bloom, int m, int mid, int k) {
int bough = 0, cnt = 0;
for(int i = 0; i < bloom.size(); i++) {
if(bloom[i] > mid) {
cnt = 0;
} else if(++cnt >= k) {
cnt = 0;
bough++;
}
}
if(bough >= m) return true;
else return false;
}
int minDays(vector<int>& bloom, int m, int k) {
int n = bloom.size();
if((long)m * k > n) return -1;
int l = 1, r = (int) 1e9, result;
while(l <= r) {
int mid = l + (r - l) / 2;
if(isValid(bloom, m, mid, k)) {
result = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return result;
}
1 : Method
int isValid(vector<int> &bloom, int m, int mid, int k) {
This function checks if it's possible to make `m` bouquets with at least `k` adjacent flowers blooming on or before day `mid`.
2 : Variable Initialization
int bough = 0, cnt = 0;
Two variables are initialized: `bough` to count the number of bouquets and `cnt` to track the number of consecutive blooming flowers.
3 : Loop
for(int i = 0; i < bloom.size(); i++) {
This loop iterates over the `bloom` array to check the blooming status of each flower.
4 : Condition
if(bloom[i] > mid) {
If the flower blooms after day `mid`, we reset the counter (`cnt = 0`) since no more flowers can be added to the current bouquet.
5 : Reset Counter
cnt = 0;
Resetting the counter (`cnt`) ensures we start counting the next set of consecutive flowers.
6 : Condition
} else if(++cnt >= k) {
If `cnt` reaches `k`, we have enough consecutive flowers to form a bouquet, so we increment the bouquet count (`bough++`).
7 : Reset Counter
cnt = 0;
Resetting the counter (`cnt`) to 0 after forming a bouquet.
8 : Increment Bouquets
bough++;
We increment the `bough` count when a bouquet is formed with `k` consecutive flowers.
9 : Return
if(bough >= m) return true;
If we have formed at least `m` bouquets, return `true` to indicate that it's possible to form the bouquets within the given conditions.
10 : Return
else return false;
If fewer than `m` bouquets were formed, return `false` to indicate that it's not possible to meet the requirement.
11 : Method
int minDays(vector<int>& bloom, int m, int k) {
The `minDays` function finds the minimum day on which at least `m` bouquets can be made, each with `k` adjacent blooming flowers.
12 : Variable Initialization
int n = bloom.size();
The size of the `bloom` array is stored in `n`, representing the total number of flowers.
13 : Condition
if((long)m * k > n) return -1;
If the total number of flowers is less than `m * k`, it is impossible to form `m` bouquets, so the function returns `-1`.
14 : Variable Initialization
int l = 1, r = (int) 1e9, result;
Initialize the binary search bounds: `l` is the minimum day (1), `r` is a large upper bound (1e9), and `result` will hold the answer.
15 : Binary Search
while(l <= r) {
Start the binary search loop, which continues as long as the lower bound `l` is less than or equal to the upper bound `r`.
16 : Mid Calculation
int mid = l + (r - l) / 2;
Calculate the middle point `mid` between `l` and `r` to check the possibility of forming `m` bouquets within `mid` days.
17 : Condition
if(isValid(bloom, m, mid, k)) {
Check if it's possible to form `m` bouquets within `mid` days using the `isValid` function.
18 : Result Update
result = mid;
If it's possible to form `m` bouquets within `mid` days, update the `result` with `mid` and continue searching for smaller values of `mid`.
19 : Adjust Search Bounds
r = mid - 1;
Adjust the upper bound `r` to `mid - 1` to search for smaller days that might still work.
20 : Else Condition
} else {
If it's not possible to form `m` bouquets within `mid` days, we need to increase the day count.
21 : Adjust Search Bounds
l = mid + 1;
Adjust the lower bound `l` to `mid + 1` to search for larger days.
22 : Return Result
return result;
Return the result, which is the minimum day when at least `m` bouquets can be made.
Best Case: O(n log(max(bloomDay))) for the binary search and validation check.
Average Case: O(n log(max(bloomDay)))
Worst Case: O(n log(max(bloomDay)))
Description: The time complexity is dominated by the binary search step and the validation step, both of which are O(n).
Best Case: O(n)
Worst Case: O(n) for storing the bloomDay array.
Description: The space complexity is O(n) due to the input array.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus