Solution Approach

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

Early Termination: Before starting the binary search, we check if it's even possible to make m bouquets. If m * k > len(bloomDay), there aren't enough flowers, so we return -1 immediately.

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

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

Binary Search Template: We use the standard binary search template to find the first day where feasible(day) returns True:

left, right = min(bloomDay), max(bloomDay)
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if feasible(mid):
        first_true_index = mid
        right = mid - 1  # Search for earlier day
    else:
        left = mid + 1

return first_true_index

The key insight is that the feasibility forms a monotonic pattern: [False, False, ..., False, True, True, ..., True]. Once we can make m bouquets on day d, we can always make them on any later day. We track first_true_index to remember the earliest valid day found, and use right = mid - 1 to continue searching for an even earlier day.

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: Initialize binary search

• left = min(bloomDay) = 7
• right = max(bloomDay) = 12
• first_true_index = -1

Step 2: Binary search process (while left <= right)

Iteration 1: left = 7, right = 12, mid = 9

• Check feasible(9):
• Bloomed status: [Yes, Yes, Yes, Yes, No, Yes, Yes] (flower at index 4 blooms on day 12)
• Traverse array:
  • Indices 0-2: 3 consecutive flowers → bouquet #1, reset counter
  • Index 3: 1 consecutive flower
  • Index 4: Not bloomed, reset counter
  • Indices 5-6: 2 consecutive flowers (not enough)
• Total bouquets: 1, need 2
• Result: False, set left = mid + 1 = 10

Iteration 2: left = 10, right = 12, mid = 11

• Check feasible(11):
• Same as day 9 (flower at index 4 still hasn't bloomed on day 11)
• Total bouquets: 1
• Result: False, set left = mid + 1 = 12

Iteration 3: left = 12, right = 12, mid = 12

• Check feasible(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, set first_true_index = 12, right = mid - 1 = 11

Iteration 4: left = 12, right = 11

• left > right, exit loop

Step 3: Return result Return first_true_index = 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 7 to 12.

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. Using Wrong Binary Search Template Variant

A common mistake is using the while left < right with right = mid variant instead of the standard template with first_true_index tracking.

Incorrect approach:

# WRONG: Different template variant
while left < right:
    mid = (left + right) // 2
    if feasible(mid):
        right = mid
    else:
        left = mid + 1
return left

Correct approach: Use the standard template with first_true_index to track the answer:

first_true_index = -1
while left <= right:
    mid = (left + right) // 2
    if feasible(mid):
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1
return first_true_index

2. 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 feasible_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.

3. 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 feasible_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.

4. Integer Overflow in Early Termination Check

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

Prevention: Cast to long before multiplication: if (long) m * k > bloomDay.length.

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.