Scale Engineer

Minimum Number of Days to Make m Bouquets

Med
#1368Time: O(D * N), where D is the range of days (`maxDay - minDay`) and N is the length of `bloomDay`. The outer loop iterates through all possible days, and for each day, we perform a linear scan of the `bloomDay` array. Since `maxDay` can be up to 10^9, this approach is too slow.Space: O(1). We only use a few variables for counting, so the space required is constant.1 company
Algorithms
Binary Search
Data structures
Array
Companies
Navi

Prompt

You are given an integer array bloomDay, an integer m and an integer k.

You want to make m bouquets. To make a bouquet, you need to use k adjacent flowers from the garden.

The garden consists of n flowers, the ith flower will bloom in the bloomDay[i] and then can be used in exactly one bouquet.

Return the minimum number of days you need to wait to be able to make m bouquets from the garden. If it is impossible to make m bouquets return -1.

 

Example 1:

Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
Output: 3
Explanation: Let us see what happened in the first three days. x means flower bloomed and _ means flower did not bloom in the garden.
We need 3 bouquets each should contain 1 flower.
After day 1: [x, _, _, _, _]   // we can only make one bouquet.
After day 2: [x, _, _, _, x]   // we can only make two bouquets.
After day 3: [x, _, x, _, x]   // we can make 3 bouquets. The answer is 3.

Example 2:

Input: bloomDay = [1,10,3,10,2], m = 3, k = 2
Output: -1
Explanation: We need 3 bouquets each has 2 flowers, that means we need 6 flowers. We only have 5 flowers so it is impossible to get the needed bouquets and we return -1.

Example 3:

Input: bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
Output: 12
Explanation: We need 2 bouquets each should have 3 flowers.
Here is the garden after the 7 and 12 days:
After day 7: [x, x, x, x, _, x, x]
We can make one bouquet of the first three flowers that bloomed. We cannot make another bouquet from the last three flowers that bloomed because they are not adjacent.
After day 12: [x, x, x, x, x, x, x]
It is obvious that we can make two bouquets in different ways.

 

Constraints:

  • bloomDay.length == n
  • 1 <= n <= 105
  • 1 <= bloomDay[i] <= 109
  • 1 <= m <= 106
  • 1 <= k <= n

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves simulating the process day by day. We can iterate through each possible day, starting from the earliest possible bloom day, and for each day, we check if we can form the required m bouquets. The first day on which this condition is met will be our minimum number of days.

Algorithm

    1. First, handle the edge case: if the total number of flowers required (m * k) is greater than the number of flowers available (n), it's impossible. Return -1.
    1. Find the minimum (minDay) and maximum (maxDay) values in the bloomDay array. The answer must lie within this range.
    1. Iterate through each day d from minDay to maxDay.
    1. For each day d, check if it's possible to make m bouquets.
    • a. Initialize a counter for bouquets made (bouquets = 0) and a counter for consecutive bloomed flowers (adjacentFlowers = 0).
    • b. Iterate through the bloomDay array.
    • c. If a flower bloomDay[i] has bloomed by day d (i.e., bloomDay[i] <= d), increment adjacentFlowers.
    • d. If bloomDay[i] > d, the sequence of adjacent flowers is broken, so reset adjacentFlowers to 0.
    • e. If adjacentFlowers reaches k, it means we can form a bouquet. Increment bouquets and reset adjacentFlowers to 0.
    1. If after checking day d, the number of bouquets is greater than or equal to m, then d is the minimum number of days. Return d.
    1. If the loop completes without finding a suitable day, it means it's impossible to make m bouquets. Return -1.

Walkthrough

The brute-force method directly translates the problem statement into a simulation. We test every single day from the earliest bloom time to the latest. For a given day d, we can determine which flowers have bloomed. Then, we can scan the garden to count how many bouquets of k adjacent bloomed flowers can be formed. If we can form m or more bouquets, we've found our answer. Since we are checking days in increasing order, the first day that satisfies the condition is guaranteed to be the minimum.

public class Solution {    public int minDays(int[] bloomDay, int m, int k) {        int n = bloomDay.length;        if ((long) m * k > n) {            return -1;        }         int minDay = Integer.MAX_VALUE;        int maxDay = Integer.MIN_VALUE;        for (int day : bloomDay) {            minDay = Math.min(minDay, day);            maxDay = Math.max(maxDay, day);        }         for (int day = minDay; day <= maxDay; day++) {            if (canMakeBouquets(bloomDay, m, k, day)) {                return day;            }        }         return -1;    }     private boolean canMakeBouquets(int[] bloomDay, int m, int k, int currentDay) {        int bouquets = 0;        int flowers = 0;        for (int i = 0; i < bloomDay.length; i++) {            if (bloomDay[i] <= currentDay) {                flowers++;            } else {                flowers = 0;            }             if (flowers == k) {                bouquets++;                flowers = 0;            }        }        return bouquets >= m;    }}

This approach is straightforward but inefficient due to the potentially large range of days we have to check.

Complexity

Time

O(D * N), where D is the range of days (`maxDay - minDay`) and N is the length of `bloomDay`. The outer loop iterates through all possible days, and for each day, we perform a linear scan of the `bloomDay` array. Since `maxDay` can be up to 10^9, this approach is too slow.

Space

O(1). We only use a few variables for counting, so the space required is constant.

Trade-offs

Pros

  • Simple to understand and implement.

  • Directly models the problem's conditions.

Cons

  • Extremely inefficient for large ranges of bloomDay values.

  • Not a feasible solution for the given constraints and will cause a Time Limit Exceeded error.

Solutions

class Solution { public int minDays ( int [] bloomDay , int m , int k ) { if ( m * k > bloomDay . length ) { return - 1 ; } int min = Integer . MAX_VALUE , max = Integer . MIN_VALUE ; for ( int bd : bloomDay ) { min = Math . min ( min , bd ); max = Math . max ( max , bd ); } int left = min , right = max ; while ( left < right ) { int mid = ( left + right ) >>> 1 ; if ( check ( bloomDay , m , k , mid )) { right = mid ; } else { left = mid + 1 ; } } return left ; } private boolean check ( int [] bloomDay , int m , int k , int day ) { int cnt = 0 , cur = 0 ; for ( int bd : bloomDay ) { cur = bd <= day ? cur + 1 : 0 ; if ( cur == k ) { cnt ++; cur = 0 ; } } return cnt >= m ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem