How to Answer: What are the minimum number of days to make bouquets?
Advice and answer examples written specifically for a Java Intermediate Level Binary Search job interview.
2. What are the minimum number of days to make bouquets?
This interview question concentrates on the developer's skills with Java binary search and loops.
You own a garden which has flowers arranged in a row. The flowers have not bloomed yet. You need to make m bouquets. To make one bouquet, you need k adjacent flowers from the garden. For the ith flower, the adjacent flowers are (i - 1)th and (i + 1)th flowers.
The garden has n flowers. You are given an array bloomDay of size n. The ith flower will bloom on day bloomDay[i]. One flower can be used to make at most one bouquet.
Your task is to find the minimum number of days you need to wait so that enough flowers have bloomed to make m bouquets. If it is impossible to make m bouquets, return -1.
/*Example*/
bloomDay = [1, 10, 3, 10, 2] m = 3 k = 1
expected output = 3
explanation:- x represents that the flower at that position has bloomed
after day 1:- [x, _, _, _, _]
after day 2:- [x, _, _, _, x]
after day 3:- [x, _, x, _, x] After 3 days, we can make 3 bouquets.Solution:
We can use binary search for it. Let’s say min is the minimum of days required. If we are asked:
â— Can we make m bouquets in days less than min? The answer is definitely no.
â— Can we make m bouquets in days greater than or equal to min? The answer is definitely yes.
0 1 … min - 1 min min + 1 … max-possible
F F F F T T T T
We can do the binary search from 0 to max-possible. We will check if we can make m bouquets in a mid number of days or not. We will update the variables accordingly as in the code. The value of max-possible is the maximum of bloomDay array i.e. the maximum number of days that a flower will take to bloom.
To check if we can make m bouquets in a mid number of days or not, we will use canMake function. We will see which flowers will bloom on or before the day days. After checking bloomed flowers, we see the number of adjacent flowers and then count the number of bouquets that can be formed using those adjacent flowers.
class Solution {
public int minDays(int[] bloomDay, int m, int k) {
if (m * k > bloomDay.length) {
return -1;
}
int left = 1;
int right = Arrays.stream(bloomDay).max().getAsInt();
while(left < right) {
int mid = left + (right -left) / 2;
if (canMake(mid, bloomDay, m, k)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
public boolean canMake(int days, int[] bloomDays, int m, int k) {
int bouquetsMade = 0;
int adjFlowers = 0;
for (int day : bloomDays) {
// the current flower has not
// bloomed yet before or on `day`
if (day > days) {
adjFlowers = 0;
continue;
}
// the flower has bloomed
bouquetsMade += (int)Math.floor((adjFlowers + 1) / k);
adjFlowers = (adjFlowers + 1) % k;
}
return bouquetsMade >= m;
}
}Time complexity- O(log (max-possible))
Space complexity- O(1)
Written by Jennie Taylor on May 22nd, 2021