Domain 2MediumMEDIUM

Minimum Number of Days to Make m Bouquets

LeetCode problem 1482: Minimum Number of Days to Make m Bouquets (medium).

Domain: medium•Updated: 2026-09-17
#Array#Binary Search

Problem Breakdown

We are given an array of bloom days for each flower in a garden and need to determine the minimum number of days required to create exactly m bouquets, where each bouquet requires k adjacent bloomed flowers.

Inputs:

  • bloomDay: List of integers representing when each flower blooms.
  • m: Target number of bouquets.
  • k: Number of consecutive flowers needed per bouquet.

Outputs:

  • Minimum integer days required, or -1 if impossible.

Implicit Constraints & Edge Cases:

  • Impossible Case: If the total available flowers (n) is less than the total flowers required for all bouquets (m * k), it’s physically impossible to form m bouquets regardless of time passed. We must return -1 immediately in this case.
  • Range of Days: The bloom days can be up to 10910^9. Iterating day-by-day is computationally expensive (O(109)O(10^9)). However, the relationship between “days waited” and “bouquets made” is monotonic (waiting longer never hurts), which allows for optimization.
  • Adjacency: Flowers must be adjacent in the original array order to form a bouquet; gaps reset the count of consecutive flowers available for that specific bouquet.

Intuition

A brute-force approach would iterate through every possible day from 1 up to 10910^9. For each day, we check if m bouquets can be formed. This is inefficient because checking takes linear time with respect to array size (O(n)O(n)), and the loop runs for potentially billions of iterations.

However, observe this property: If it is possible to make the required bouquets in DD days, it will definitely be possible in any day greater than DD. Conversely, if we cannot do it in DD days, we certainly can’t do it in fewer days. This monotonicity allows us to use Binary Search on the Answer.

Instead of searching for a solution within the array indices or values directly, we search for the minimum valid day value within the range [min(bloomDay), max(bloomDay)]. We narrow down this window until finding the smallest day that satisfies our condition. The check function inside binary search runs in O(n)O(n) time.

Approach

  1. Validation: First, calculate total flowers needed (m * k). If len(bloomDay) < m * k, return -1 immediately as it’s impossible to gather enough adjacent groups.
  2. Binary Search Setup:
    • Define search space: low = minimum bloom day in array (or 0), high = maximum bloom day in array (or 10910^9). A tighter bound is better, so we use min/max of the input list.
  3. Binary Search Loop:
    • While low < high:
      • Calculate mid = low + (high - low) // 2.
      • Check if it’s possible to make bouquets in mid days using a helper function.
  4. Check Function Logic (can_make_bouquets(day)):
    • Iterate through the garden array once (O(n)O(n)).
    • Maintain a counter for consecutive bloomed flowers (consecutive_count).
    • If current flower blooms on or before day, increment consecutive_count.
    • Else, reset consecutive_count to 0.
    • Whenever consecutive_count == k:
      • We found a valid bouquet group. Increment total bouquets made (bouquet_count).
      • Reset consecutive_count to 0 (since these flowers are used).
    • If at any point bouquet_count >= m, return True immediately for optimization, though checking the end is also fine given constraints.
  5. Update Search Space:
    • If check returns True: We can try fewer days (high = mid).
    • If False: Need more time (low = mid + 1).
  6. Result: Return low as the minimum valid day.

Complexity Analysis

  • Time Complexity: O(n⋅log⁡(max_bloom))O(n \cdot \log(\text{max\_bloom})).
    • The binary search runs over the range of bloom days (up to 10910^9), which is ≈30\approx 30 iterations (log⁡2(109)\log_2(10^9)).
    • Inside each iteration, we scan the array once: O(n)O(n).
    • Given n≤105n \le 10^5, this results in roughly 3⋅1063 \cdot 10^6 operations, which fits well within typical time limits (usually ∼108\sim 10^8 ops/sec).
  • Space Complexity: O(1)O(1) auxiliary space. We only use a few integer variables for counting and pointers; no additional data structures are allocated proportional to input size.

Solution

def minDays(bloomDay, m, k):
    n = len(bloomDay)
    
    # Edge case: Impossible if we don't have enough flowers total
    if m * k > n:
        return -1
    
    # Binary search range for the answer (days to wait)
    low = min(bloomDay)
    high = max(bloomDay)
    
    def can_make_bouquets(day):
        bouquets_made = 0
        consecutive_count = 0
        
        for bloom in bloomDay:
            if bloom <= day:
                consecutive_count += 1
                # If we have k adjacent flowers, form a bouquet
                if consecutive_count == k:
                    bouquets_made += 1
                    consecutive_count = 0
            else:
                consecutive_count = 0
        
        return bouquets_made >= m
    
    while low < high:
        mid = (low + high) // 2
        if can_make_bouquets(mid):
            # Possible in 'mid' days, try to find a smaller valid day
            high = mid
        else:
            # Not possible yet, need more time
            low = mid + 1
            
    return low

# Example usage (uncomment for testing)
# print(minDays([1,10,3,10,2], 3, 1))   # Output: 3

Edge Cases Handled

  • Impossible Configuration: The check if m * k > n ensures we return -1 immediately if the total flower count is insufficient to form even one bouquet per requirement.
  • Large Bloom Days: By using binary search on values up to 10910^9 rather than iterating days, we avoid Time Limit Exceeded (TLE) errors associated with large integer ranges.
  • Single Bouquet Requirement (m=1m=1): The logic holds naturally; the loop will find the minimum day where k adjacent flowers bloom.
  • All Flowers Bloom Same Day: Binary search converges to that specific value correctly as both bounds tighten around it.