Leetcode 1482. Minimum Number of Days to Make m Bouquets

Let's understand what we're being asked to do. We have an array bloomDay where bloomDay[i] represents the day when flower i blooms. We need to form m bouquets, where each bouquet requires k adjacent flowers that have all bloomed.

For example, with bloomDay = [1,10,3,10,2], m = 3, k = 1: On day 1, flower 0 blooms. On day 2, flowers 0 and 4 have bloomed. On day 3, flowers 0, 2, and 4 have bloomed - we can make 3 bouquets (each needs only 1 flower). Answer: day 3.

Now consider bloomDay = [1,10,3,10,2], m = 3, k = 2: We need 3 bouquets, each requiring 2 adjacent flowers. Even on day 10 (all flowers bloomed), we can't form 3 bouquets of 2 adjacent flowers from 5 flowers. Answer: -1.

Key constraint: Flowers must be adjacent (consecutive positions in the array) to form a bouquet. We can't pick flowers from different parts of the array.

Edge cases: What if m * k > n (impossible to form enough bouquets)? Return -1. What if multiple days work? Return the minimum day.

The brute force approach checks every possible day from 1 to max(bloomDay) sequentially. For each day, scan the bloomDay array to count how many contiguous segments of k bloomed flowers exist. If we can form at least m bouquets, return that day. This approach is simple but inefficient because it checks every single day, even though many days will give the same result.

def min_days_to_bloom(bloomDay, m, k):
    """
    Brute force: Check every day from 1 to max(bloomDay) sequentially.
    For each day, count how many k-length contiguous bloomed segments exist.
    """
    n = len(bloomDay)
    
    # Impossible case: need more flowers than available
    if m * k > n:
        return -1
    
    # Find the maximum day to check
    max_day = max(bloomDay)
    
    # Check each day from 1 to max_day
    for day in range(1, max_day + 1):
        # Count how many bouquets we can make on this day
        bouquets = 0
        consecutive_bloomed = 0
        
        # Scan through the array to find k-length bloomed segments
        for i in range(n):
            # Check if flower at position i has bloomed by this day
            if bloomDay[i] <= day:
                consecutive_bloomed += 1
                # If we have k consecutive bloomed flowers, make a bouquet
                if consecutive_bloomed == k:
                    bouquets += 1
                    consecutive_bloomed = 0
            else:
                # Reset counter if flower hasn't bloomed
                consecutive_bloomed = 0
        
        # Check if we can make at least m bouquets
        if bouquets >= m:
            return day
    
    return -1

The key insight is that if we can make m bouquets on day D, we can also make m bouquets on any day after D (more flowers will have bloomed).

This creates a monotonic property: there's a threshold day where the answer changes from 'impossible' to 'possible'. Days before this threshold fail, days after succeed.

When we have a sorted search space with a clear 'yes/no' boundary, we can use binary search on the answer.

Instead of checking every day from 1 to max(bloomDay), we can eliminate half the days with each check, reducing from O(n) checks to O(log n) checks.

Think of it like finding the exact temperature where water freezes. Below 0°C it's frozen, above 0°C it's liquid.

You don't need to test every temperature from -100°C to +100°C. Instead, test the middle temperature, see if it's frozen or liquid, and narrow your search to the relevant half. The monotonic property (frozen → liquid, never liquid → frozen → liquid) makes this efficient.

For each candidate day, we need to check: 'Can we form m bouquets by this day?' This check involves scanning the array to count contiguous bloomed segments of length k.

The optimal approach uses binary search on the answer space (days from 1 to max(bloomDay)). For each candidate day (mid), we check feasibility by scanning the array once to count contiguous bloomed segments of length k. If we can form at least m bouquets, search the left half for an earlier day; otherwise, search the right half. This leverages the monotonic property: if day D works, all days after D also work.

def min_days_to_bloom(bloomDay, m, k):
    """
    Find minimum day to form m bouquets of k adjacent bloomed flowers.
    Binary search on days, check feasibility by counting k-length segments.
    """
    n = len(bloomDay)
    
    # Impossible case: need more flowers than available
    if m * k > n:
        return -1
    
    # Binary search bounds: day 1 to max bloom day
    left = 1
    right = max(bloomDay)
    result = -1
    
    # Binary search for minimum feasible day
    while left <= right:
        mid = (left + right) // 2
        
        # Check if we can form m bouquets by day mid
        bouquets = 0
        flowers = 0
        
        # Scan array to count contiguous bloomed segments
        for day in bloomDay:
            if day <= mid:
                # Flower has bloomed by day mid
                flowers += 1
                if flowers == k:
                    # Completed one bouquet
                    bouquets += 1
                    flowers = 0
            else:
                # Flower not bloomed, reset counter
                flowers = 0
        
        # Check if we formed enough bouquets
        if bouquets >= m:
            # Feasible: try earlier day
            result = mid
            right = mid - 1
        else:
            # Not feasible: need later day
            left = mid + 1
    
    return result

• Binary search on answer space: When a problem asks for a "minimum/maximum value that satisfies a condition" and you can verify feasibility in reasonable time, think binary search on the answer rather than the input array - here we search days [1, max(bloomDay)] instead of array indices.
• Greedy feasibility checking: The verification function uses a greedy scan to count bouquets by tracking consecutive bloomed flowers - reset your counter when the chain breaks and increment bouquet count when reaching k adjacent flowers, making each check O(n) instead of exploring all combinations.
• Monotonicity recognition: Binary search works here because of the monotonic property - if you can make m bouquets on day X, you can definitely make them on day X+1 or later. Always verify this "if true at X, then true for all Y > X" property before applying binary search.
• Overflow prevention in constraints: Check impossibility upfront with `m * k > n` before starting binary search - this prevents wasted computation and handles the edge case where the problem is unsolvable, but be careful with integer overflow when m and k are large (use `m > n/k` instead).
• Search space boundary selection: Set binary search bounds as `left = min(bloomDay)` and `right = max(bloomDay)` rather than arbitrary values - this tightens the search space and ensures you're only checking valid day values that actually appear in the problem.
• Simulation-based optimization pattern: This "binary search + simulation" pattern applies broadly to resource allocation problems (minimum capacity, minimum time, minimum speed) where direct calculation is hard but checking "is X enough?" is straightforward - look for this in scheduling, capacity, and threshold problems.