Coding

Minimum days to make M bouquets

Asked at

Amazon

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The 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) {

    }
}

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

If m times k exceeds the number of flowers, return minus one immediately; use a wide integer for this product. Otherwise binary-search a candidate day between the minimum and maximum bloom days. To test feasibility, scan the array and count consecutive flowers whose bloom day is at most the candidate. When the run reaches k, form one bouquet, increment the bouquet count, and reset the run to zero because flowers cannot be reused. A flower not yet bloomed resets the run as well. If at least m bouquets can be formed, that day is feasible, and every later day is also feasible, establishing monotonicity. Therefore shrink high on feasible days and raise low on infeasible days. The scan costs O(n) and there are O(log range) candidate days, for O(n log range) time and O(1) extra space.

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

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question