Minimum days to make M bouquets
AmazonThe problem
Given n roses and an array nums where nums[i] denotes that the 'ith' rose will bloom on the nums[i]th day, only adjacent bloomed roses can be picked to make a bouquet. Exactly k adjacent bloomed roses are required to make a single bouquet. Find the minimum number of days required to make at least m bouquets, each containing k roses. Return -1 if it is not possible.
Input: n = 8, nums = [7, 7, 7, 7, 13, 11, 12, 7], m = 2, k = 3 Output: 12 Explanation: On the 12th 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.
Input: n = 5, nums = [1, 10, 3, 10, 2], m = 3, k = 2 Output: -1 Explanation: If we want to make 3 bouquets of 2 flowers each, we need at least 6 flowers. But we are given only 5 flowers, so, we cannot make the bouquets.
Input: n = 5, nums = [1, 10, 3, 10, 2], m = 3, k = 1
- 1 <= n <= 105
- 1 <= nums[i] <= 109
- 1 <= m <= 106
- 1 <= k <= n
cpp
class Solution {
public:
int roseGarden(int n,vector<int> nums, int k, int m) {
}
};java
class Solution {
public int roseGarden(int n, int[] nums, int k, int m) {
}
}python
class Solution:
def roseGarden(self, n, nums, k, m):javascript
class Solution {
roseGarden(n, nums, k, m) {
}
}csharp
public class Solution {
public int RoseGarden(int n, List<int> nums, int k, int m) {
}
}go
func roseGarden(n int, nums []int, k int, m int) int {
}Stuck? Show a way to structure it+
- 01Reject if m times k exceeds n.
- 02Binary-search between minimum and maximum bloom day.
- 03For a day, scan consecutive bloomed flowers.
- 04Form a bouquet each time a run reaches k.
- 05Use feasibility to narrow the day.
Reference answer
Then expect these follow-ups
Why does the feasibility predicate remain monotonic?
Tests: correctness reasoning
How would you return the actual bouquet positions?
Tests: implementation extension
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question