#1482

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Minimum Number of Days to Make m Bouquets

Determine the minimum number of days required to make m bouquets using k adjacent flowers efficiently with binary search.

array binary search

Problem Statement

You are given an integer array bloomDay, where bloomDay[i] represents the day the ith flower will bloom. You are also given integers m and k. Your task is to determine the minimum number of days needed to make m bouquets, where each bouquet requires k adjacent flowers that have bloomed.

Each flower can only be used in one bouquet. If it is impossible to make m bouquets given the bloomDay array, return -1. Focus on leveraging binary search over the possible days to find the earliest day that satisfies the bouquet requirement.

Examples

Example 1

Input: bloomDay = [1,10,3,10,2], m = 3, k = 1

Output: 3

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

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

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

Solution Approach

Binary Search on Days

Use the minimum and maximum bloom days as the search range. At each midpoint day, check if m bouquets can be made using k adjacent bloomed flowers. Adjust the search range based on whether the condition is satisfied to find the minimum valid day.

Bouquet Validation Check

Iterate through bloomDay and count consecutive bloomed flowers for the given day. Each time k adjacent bloomed flowers are found, increment the bouquet count and reset the adjacency counter. Stop early if the required m bouquets are reached.

Edge Cases and Early Termination

Return -1 immediately if m * k exceeds the number of flowers. Handle cases where all flowers bloom on the same day or when k equals 1 efficiently, as they simplify the adjacency check. This prevents unnecessary iteration in extreme cases.

Complexity Analysis

Metric	Value
Time	O(N \log D)
Space	O(1)

Time complexity is O(N \log D) because binary search reduces the range of days while validating bouquets takes O(N) for each check. Space complexity is O(1) since no additional structures proportional to N are required.

What Interviewers Usually Probe

Check if the candidate recognizes the binary search over valid answer space pattern.
Watch if they correctly handle adjacency constraints in the bouquet check.
See if they catch cases where the total flowers are insufficient early.

Common Pitfalls or Variants

Common pitfalls

Miscounting adjacent flowers and resetting the counter incorrectly, leading to wrong bouquet counts.
Failing to handle the case where m * k exceeds bloomDay.length and returning an incorrect minimum day.
Iterating sequentially through days instead of using binary search, resulting in TLE for large arrays.

Follow-up variants

Find the maximum number of bouquets possible by a given day instead of the minimum day.
Change adjacency requirement to allow non-consecutive flowers with a minimum gap between them.
Determine the earliest day to make bouquets when each bouquet can use variable numbers of adjacent flowers.

FAQ

What is the best approach to solve Minimum Number of Days to Make m Bouquets?

Use binary search over the possible days combined with a consecutive flower check for bouquets. This efficiently narrows the minimum day.

How do I handle cases when there are not enough flowers to make m bouquets?

Immediately return -1 if m * k exceeds the total number of flowers to avoid unnecessary computation.

Why is binary search used in this problem?

Binary search efficiently finds the minimum day where m bouquets can be formed, avoiding a sequential day-by-day check which is too slow.

How do I count bouquets correctly?

Iterate through bloomDay for the candidate day, increment consecutive flower count, and form a bouquet each time k adjacent flowers bloom, resetting the counter.

What edge cases should I watch for?

Watch for cases where k equals 1, all flowers bloom on the same day, or m * k exceeds the number of flowers, as these can simplify or invalidate the solution.

terminal

Solution

Solution 1: Binary Search

According to the problem description, if a day $t$ can satisfy making $m$ bouquets, then for any $t' > t$, it can also satisfy making $m$ bouquets. Therefore, we can use binary search to find the minimum day that satisfies making $m$ bouquets.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        def check(days: int) -> int:
            cnt = cur = 0
            for x in bloomDay:
                cur = cur + 1 if x <= days else 0
                if cur == k:
                    cnt += 1
                    cur = 0
            return cnt >= m

        mx = max(bloomDay)
        l = bisect_left(range(mx + 2), True, key=check)
        return -1 if l > mx else l

Continue Practicing

#1477 find two non overlapping sub arrays each with target sum #1488 avoid flood in the city #1498 number of subsequences that satisfy the given sum condition