Problem

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.

Examples

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.

Solution

bloomDay represents an array - where each cell represents day on which flower blooms. Each cell has just 1 flower.

We need k flowers to make 1 bouquets, and we need to form m bouquets.

Method 1 - Naive

The naive approach can be:

  1. Initialize the range of days:
    • Track the minimum and maximum days within bloomDay.
  2. Iterate through each day:
    • Check each day from the minimum bloom day to the maximum bloom day.
    • On each day, count how many bouquets can be made.
  3. Count Bouquets for Each Day:
    • For each day, iterate through the bloomDay array to check if the number of consecutive bloomed flowers allows us to make m bouquets of k consecutive flowers.
  4. Return the First Valid Day:
    • Return the first day that allows making at least m bouquets, or return -1 if no day satisfies the requirement.

Complexity

  • Time: O(n*m) - where n is number of elements in bloomDay and m is max value in bloomDays
  • Space: O(1)

Method 2 - Binary Search

Algorithm

Lets take the bloomDay = [1, 10, 2, 9, 3, 8, 4, 7, 5, 6], m = 4, k = 2, to understand the logic.

1. Initial Check

If m * k exceeds the length of the bloomDay array, it’s impossible to make m bouquets, so return -1. len(bloomDay) = 10, m * k = 8. So, we can actually form the bouquets.

2. Determine search range

The minimum day low will be the earliest day any flower blooms (min(bloomDay)) and the maximum day high will be the latest day (max(bloomDay)). From low = 1, high = 10. In Leetcode, people also use constraint constraints like low = 1 and high = 10 ^ 9, but upto you.

I prefer former approach, then we are less dependant on constraints.

3. Perform the binary search on the days

We can only make bouquets with flowers that have bloomed and are adjacent to other bloomed flowers. For example, lets say on day 8, we will have flower bed as:

[𑁍, 10, 𑁍, 9, 𑁍, 𑁍, 𑁍, 𑁍, 𑁍, 𑁍]

We can only make 3 bouquet due to adjacency - denoted by {} -

[𑁍, 10, 𑁍, 9, {𑁍, 𑁍}, {𑁍, 𑁍}, {𑁍, 𑁍}]

So we need to search k adjacent flowers to form 1 bouquet, and we have to do it m times.

Problem - For a given day d, can we make m bouquets using k adjacent flowers each? If yes, is that the smallest such day possible?

  • If no, that means numBouq < m, that means we have to wait for more days for flower to bloom, and we have to set left = mid + 1
  • If yes, that means numBouq >= m, that means we have potential answer, but can we find smaller answer, and we have to set right = mid - 1

In eg. we randomly chose 8, but we can do it using binary search, instead of linearly doing it for all the days.

Also, programmatically, we can check if we can pick ith flower or not if bloomDay[i] <= currentDay.

bloomDay = [1, 10, 2, 9, 3, 8, 4, 7, 5, 6]
m = 4
k = 2
low = 1, high = 10
Iteration 1

Lets denote ⚘ for bloomed and ✘ for not bloomed.

low = 1, high = 10 => mid = (1 + 10) / 2 = 5

Can we make 4 bouquets of 2 flowers on day 5?

Lets look at bloomDay visually wher bloomDay[i] <= mid => flower
bloomDay = [1, 10, 2, 9, 3, 8, 4, 7, 5, 6]
           [⚘,  ✘, ⚘, ✘, ⚘, ✘, ⚘, ✘, ⚘, ✘]

i = 0, pick flower, flower = 1
i = 1, cannot pick flower, flower = 0
i = 2, pick flower, flower = 1
...
We cannot form any bouquets. Hence we have to increase the days.

Adjust low = mid + 1 = 6
Iteration 2
low = 6, high = 10 => mid = (6 + 10) / 2 = 8

Can we make 4 bouquets of 2 flowers on day 8?
bloomDay = [1, 10, 2, 9, 3, 8, 4, 7, 5, 6]
           [⚘,  ✘, ⚘, ✘, ⚘, ⚘, ⚘, ⚘, ⚘, ⚘]

0 -> no bouquet
1 -> no bouquet
2 -> no bouquet
3 -> no bouquet
4 -> 1 bouquet
6 -> 1 bouquet
8 -> 1 bouquet

Total 3 bouquets, but we cannot form 4 bouquets, hence we increase numDays

Adjust low = 9
Iteration 3
low = 9, high = 10 => mid = (6 + 10) / 2 = 9

Can we make 4 bouquets of 2 flowers on day 8?
bloomDay = [1, 10, 2, 9, 3, 8, 4, 7, 5, 6]
           [⚘,  ✘, ⚘, ⚘, ⚘, ⚘, ⚘, ⚘, ⚘, ⚘]

0 -> no bouquet
1 -> no bouquet
2 -> 1 bouquet
4 -> 1 bouquet
6 -> 1 bouquet
8 -> 1 bouquet

Total 4 bouquets, but we are not sure if these are min number of days possible

Adjust high = mid - 1 = 8

As, now low > high, we stop the binary search, and that answer = 9.

Code

Note that we use low <= high because we want binary search to cover every possible value in the range [low, high]. This allows for making a final check when low equals high, which is crucial in cases where the exact minimum day must be determined.

Java
public class Solution {

	public int minDays(int[] bloomDay, int m, int k) {
		if (m * k > bloomDay.length) {
			return -1;
		}

		int low = 1;
		int high = 1;

		for (int day: bloomDay) {
			high = Math.max(high, day);
		}
        int ans = - 1;
		while (low <= high) {
			int mid = low + (high - low) / 2;

			if (canMakeBouquets(bloomDay, m, k, mid)) {
                ans = mid;
				high = mid - 1;
			} else {
				low = mid + 1;
			}
		}

		return ans;
	}

	private boolean canMakeBouquets(int[] bloomDay, int m, int k, int day) {
		int bouquets = 0;
		int flowers = 0;

		for (int bloom: bloomDay) {
			if (bloom <= day) {
				flowers++;

				if (flowers == k) {
					bouquets++;
					flowers = 0;

					if (bouquets == m) {
						return true;
					}
				}
			} else {
				flowers = 0;
			}
		}

		return false;
	}

}

Complexity

  • ⏰ Time complexity: O(log(m) * n), where m is the max element in bloomDays and n is length of bloomDays. The reason is:
    • O(n) time for finding max and min element in the array
    • log(m) to perform binary search
    • O(n) time to find elements m bouquets in in bloomDay
  • 🧺 Space complexity: O(1)