Limited Time Offer:Up to 25% off Hello Interview Premium

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Low Level Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Ask The Community

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Tutor

Get Premium

Leetcode 1482. Minimum Number of Days to Make m Bouquets

Find the minimum day such that you can form at least m bouquets, each requiring k adjacent flowers that have bloomed (return -1 if impossible, e.g., when m*k > n). This is typically solved by binary searching the day and greedily scanning for k-length contiguous bloomed segments to check feasibility.

Asked at:

Amazon

DESCRIPTION

Input:

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

Output:

Explanation: On day 3, flowers at positions 0, 2, and 4 have bloomed. Since k=1, each flower forms a bouquet. We can make 3 bouquets.

Constraints:

bloomDay.length == n
1 <= n <= 10^5
1 <= bloomDay[i] <= 10^9
1 <= m <= 10^6
1 <= k <= n
If m * k > n, return -1 (impossible to form enough bouquets)

Understanding the Problem

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.

Brute Force Approach

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.

Visualization

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

Start brute force: check each day sequentially

0 / 86

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n * max(bloomDay)) For each of the max(bloomDay) possible days, we scan the array of n flowers to check feasibility. This results in O(n * max(bloomDay)) time, which can be extremely large when max(bloomDay) is up to 10^9.

Space Complexity: O(1) We only use a constant amount of extra space for counters and variables, regardless of input size.

Building Intuition

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.

Common Mistakes

Forgetting to check if m * k > n at the start - this makes the problem impossible and should return -1 immediately

Using linear search through all days instead of binary search - this times out when max(bloomDay) is large (up to 10^9)

Incorrectly counting contiguous segments - must reset the counter when encountering an unbloomed flower, not just decrement it

Off-by-one errors in binary search: when a day works, search left with 'right = mid' (not 'mid - 1') to ensure we don't skip the minimum valid day

Not handling the case where no valid day exists - the binary search should eventually converge to a day, but if that day still fails the feasibility check, return -1

Optimal Solution

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.

Visualization

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

Start: Find minimum days to make m bouquets of k adjacent flowers

0 / 83

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n * log(max(bloomDay))) Binary search on the day range takes O(log(max(bloomDay))) iterations. Each iteration requires O(n) time to scan the array and check feasibility. Total: O(n * log(max(bloomDay))). With max(bloomDay) up to 10^9, log(10^9) ≈ 30, making this much faster than the brute force.

Space Complexity: O(1) We only use a constant amount of extra space for binary search pointers (left, right, mid) and the feasibility check counters.

What We've Learned

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.

Test Your Understanding

Why is array the right data structure for this problem?

array provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Mid February, 2025

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 1482. Minimum Number of Days to Make m Bouquets

DESCRIPTION

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact