Problem Description

You have a garden with n flowers arranged in a row. Each flower blooms on a specific day given by the array bloomDay, where bloomDay[i] represents the day when the i-th flower will bloom.

Your goal is to make m bouquets, where each bouquet requires exactly k adjacent flowers that have already bloomed. Once a flower is used in a bouquet, it cannot be used in another bouquet.

The problem asks you to find the minimum number of days you need to wait before you can make m bouquets. If it's impossible to make m bouquets (for example, if there aren't enough flowers total, i.e., n < m * k), return -1.

Key constraints:

• Flowers must be adjacent (consecutive) in the garden to form a bouquet
• Each flower can only be used in one bouquet
• A flower can only be used after it has bloomed (on or after day bloomDay[i])

Example scenario: If bloomDay = [1, 10, 3, 10, 2], m = 3, and k = 1:

• On day 1: flower at index 0 blooms
• On day 2: flowers at indices 0 and 4 have bloomed
• On day 3: flowers at indices 0, 2, and 4 have bloomed (3 flowers total, can make 3 bouquets of size 1)
• Answer: 3 days

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

• We need 3 bouquets with 2 adjacent flowers each (6 flowers total)
• We only have 5 flowers, so it's impossible
• Answer: -1

Intuition

The key insight is recognizing that this problem has a monotonic property: if we can make m bouquets by day t, then we can definitely make m bouquets on any day after t (since more flowers will have bloomed). Conversely, if we cannot make m bouquets by day t, we cannot make them on any day before t either.

This monotonic property immediately suggests binary search on the answer. Instead of checking every possible day sequentially, we can search for the minimum day efficiently.

Think of it this way: imagine we have a timeline from day 1 to the maximum bloom day. At some point on this timeline, we transition from "cannot make m bouquets" to "can make m bouquets". We want to find that exact transition point.

For any given day d, we can check if it's possible to make m bouquets by:

1. Looking at which flowers have bloomed by day d (those with bloomDay[i] <= d)
2. Counting how many groups of k consecutive bloomed flowers we can find
3. Checking if we have at least m such groups

The checking process works like a sliding window: we traverse the array and count consecutive bloomed flowers. When we reach k consecutive bloomed flowers, we've found one bouquet and reset our counter. If we encounter a flower that hasn't bloomed yet, we reset the counter since the consecutive sequence is broken.

The search space for our binary search is from day 1 to the maximum value in bloomDay (since all flowers will have bloomed by then). We use binary search to efficiently find the smallest day where check(day) returns true, which gives us our answer in O(n * log(max(bloomDay))) time instead of O(n * max(bloomDay)) if we checked every day.

Learn more about Binary Search patterns.

Solution Approach

The solution implements binary search to find the minimum number of days needed to make m bouquets.

Binary Search Setup: We first determine the search space. The maximum possible answer is the maximum value in bloomDay array (when all flowers have bloomed), so we set mx = max(bloomDay). The search range is from 0 to mx + 1.

Check Function: The check(days) function determines if we can make at least m bouquets by a given day:

• Initialize cnt (bouquet counter) and cur (current consecutive flowers) to 0
• Iterate through each flower in bloomDay:
  • If bloomDay[i] <= days, the flower has bloomed, so increment cur by 1
  • Otherwise, reset cur to 0 (break in consecutive sequence)
  • When cur == k, we've found a complete bouquet:
    • Increment cnt by 1
    • Reset cur to 0 to start counting the next bouquet
• Return True if cnt >= m, otherwise False

Binary Search Execution: The code uses Python's bisect_left function with a clever trick:

l = bisect_left(range(mx + 2), True, key=check)

This searches for the leftmost position where check returns True in the range [0, mx + 1]. The key=check parameter transforms each value in the range using the check function, essentially creating a boolean array like [False, False, ..., False, True, True, ..., True], and bisect_left finds the first True.

Final Result:

• If l > mx, it means we couldn't find any valid day within the maximum bloom day, so return -1
• Otherwise, return l as the minimum number of days

Time Complexity: O(n * log(max(bloomDay))) where n is the length of the array. We perform binary search over the range of days (log(max(bloomDay))), and for each mid-point, we check if it's valid in O(n) time.

Space Complexity: O(1) as we only use a constant amount of extra space.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Example: bloomDay = [7, 7, 7, 7, 12, 7, 7], m = 2, k = 3

We need to make 2 bouquets, each requiring 3 adjacent flowers.

Step 1: Set up binary search range

• Maximum bloom day: mx = 12
• Search range: [0, 13) (0 to 12 inclusive)

Step 2: Binary search process

First iteration: mid = 6

• Check if we can make 2 bouquets by day 6:
• Bloomed status: [No, No, No, No, No, No, No] (all flowers bloom on day 7 or 12)
• Consecutive count: Can't form any bouquets
• Result: False, search right half

Second iteration: mid = 9

• Check if we can make 2 bouquets by day 9:
• Bloomed status: [Yes, Yes, Yes, Yes, No, Yes, Yes] (flower at index 4 blooms on day 12)
• Traverse array:
  • Indices 0-3: 4 consecutive bloomed flowers → make 1 bouquet from indices 0-2, reset counter
  • Index 3: 1 consecutive flower
  • Index 4: Not bloomed, reset counter
  • Indices 5-6: 2 consecutive flowers (not enough for a bouquet)
• Total bouquets: 1
• Result: False, search right half

Third iteration: mid = 11

• Check if we can make 2 bouquets by day 11:
• Same as day 9 (flower at index 4 still hasn't bloomed)
• Result: False, search right half

Fourth iteration: mid = 12

• Check if we can make 2 bouquets by day 12:
• Bloomed status: [Yes, Yes, Yes, Yes, Yes, Yes, Yes] (all flowers have bloomed)
• Traverse array:
  • Indices 0-2: 3 consecutive flowers → bouquet #1, reset counter
  • Indices 3-5: 3 consecutive flowers → bouquet #2, reset counter
  • Index 6: 1 flower (leftover)
• Total bouquets: 2
• Result: True, this is our answer

Step 3: Return result The minimum day is 12. We need to wait 12 days to make 2 bouquets of 3 adjacent flowers each.

The binary search efficiently found that day 12 is the first day when we can make the required bouquets, avoiding the need to check every single day from 1 to 12.

Solution Implementation

Time and Space Complexity

The time complexity is O(n × log M), where n is the length of the bloomDay array (number of flowers) and M is the maximum value in bloomDay (maximum blooming day).

Breaking down the analysis:

• The bisect_left function performs binary search on the range [0, mx + 1], which takes O(log M) iterations
• For each binary search iteration, the check function is called as the key function
• The check function iterates through all n elements in bloomDay, taking O(n) time
• Therefore, the total time complexity is O(n × log M)

The space complexity is O(1) as the algorithm only uses a constant amount of extra space for variables like cnt, cur, l, and mx, regardless of the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding Adjacent Flower Requirement

A common mistake is thinking that any k flowers that have bloomed can form a bouquet, rather than requiring them to be consecutive/adjacent in the garden.

Incorrect approach:

def can_make_bouquets_wrong(days: int) -> bool:
    # WRONG: Just counting total bloomed flowers
    bloomed_count = sum(1 for d in bloomDay if d <= days)
    return bloomed_count >= m * k

Correct approach: Track consecutive bloomed flowers and reset the counter when encountering an unbloomed flower or after forming a bouquet.

2. Not Resetting Counter After Making a Bouquet

Forgetting to reset the consecutive flower counter after successfully forming a bouquet leads to overcounting.

Incorrect implementation:

def can_make_bouquets_wrong(days: int) -> bool:
    bouquets_made = 0
    consecutive_bloomed = 0
  
    for bloom_day in bloomDay:
        if bloom_day <= days:
            consecutive_bloomed += 1
            if consecutive_bloomed == k:
                bouquets_made += 1
                # WRONG: Forgot to reset consecutive_bloomed!
        else:
            consecutive_bloomed = 0
  
    return bouquets_made >= m

Solution: Always reset consecutive_bloomed = 0 after incrementing bouquets_made.

3. Off-by-One Error in Binary Search Bounds

Setting incorrect initial bounds for binary search can miss edge cases.

Common mistakes:

• Starting left = 0 when the minimum should be min(bloomDay) (no flowers bloom before the earliest bloom day)
• Using left <= right with incorrect mid calculation, causing infinite loops

Correct implementation:

left, right = min(bloomDay), max(bloomDay)
while left < right:
    mid = (left + right) // 2
    if can_make_bouquets(mid):
        right = mid  # Include mid as potential answer
    else:
        left = mid + 1

4. Integer Overflow in Early Termination Check

In languages with fixed integer sizes, m * k might overflow for large values.

Prevention: Check using division instead: if m > len(bloomDay) // k: (with additional logic for when k = 0).

5. Not Handling Edge Cases

Forgetting to check if it's mathematically impossible to create the required bouquets.

Essential check:

if m * k > len(bloomDay):
    return -1

This should be done before the binary search to avoid unnecessary computation.