Pseudo-code:

text
min_day = min(bloomDay)
max_day = max(bloomDay)

for day from min_day to max_day:
    if canMakeBouquets(day, bloomDay, m, k):
        return day

return -1

Why this fails: The time complexity of this approach is $O(Range \times N)$, where $N$ is the number of flowers and $Range$ is the difference between the maximum and minimum bloom days.

• The constraints state that bloom days can be up to $10^9$.
• If $N = 10^5$ and the range is $10^9$, the algorithm performs $10^{14}$ operations.
• This results in a Time Limit Exceeded (TLE) error.

Core Insight for Minimum Number of Days to Make m Bouquets

The key intuition is moving from searching the array indices to searching the value range (days). Instead of asking "Where is the target?", we ask "Is day $X$ feasible?"

Because the feasibility function is monotonic (False, False, ..., True, True), we can binary search for the boundary where the condition switches from False to True.

The Feasibility Check (Condition Function): To verify if a specific day allows us to make m bouquets:

1. Iterate through the bloomDay array.
2. Maintain a counter for consecutive adjacent bloomed flowers.
3. If a flower's bloom day is $\le$ current check day, increment the counter.
4. If the counter reaches k, we form a bouquet. Increment the bouquet count and reset the adjacent flower counter to 0.
5. If a flower has not bloomed, the chain of adjacency is broken. Reset the adjacent flower counter to 0 immediately.

Visual Description: Imagine the bloomDay array as a row of lights. On a specific test day, some lights turn on (bloom) and others stay off.

• bloomDay: [1, 10, 3, 10, 2], check Day = 3.
• Status: [ON, OFF, ON, OFF, ON]
• We scan linearly. We look for continuous segments of "ON" lights of length k.
• If k=1, we find 3 segments.
• If k=2, we find 0 segments because the "OFF" lights break the adjacency.

This linear scan takes $O(N)$ time. By performing this check inside a binary search over the range of days, we achieve high efficiency.

Execution Flow

Let's trace Example 1: bloomDay = [1, 10, 3, 10, 2], m = 3, k = 1.

1. Initial Check: $n=5$, needed $3 \times 1 = 3$. $5 \ge 3$, so it's possible.
2. Bounds: left = 1, right = 10.
3. Iteration 1:
   • mid = 5.
   • Check day 5:
     • Index 0 (1 $\le$ 5): Bloomed. Count=1. Bouquet 1. Reset Count.
     • Index 1 (10 > 5): Not bloomed. Reset Count.
     • Index 2 (3 $\le$ 5): Bloomed. Count=1. Bouquet 2. Reset Count.
     • Index 3 (10 > 5): Not bloomed. Reset Count.
     • Index 4 (2 $\le$ 5): Bloomed. Count=1. Bouquet 3. Reset Count.
   • Total Bouquets: 3. Target: 3.
   • Condition Met. We might find a smaller day. right = 5.
4. Iteration 2:
   • Range is [1, 5]. mid = 3.
   • Check day 3:
     • Logic repeats... indices 0, 2, 4 bloom.
   • Total Bouquets: 3.
   • Condition Met. right = 3.
5. Iteration 3:
   • Range is [1, 3]. mid = 2.
   • Check day 2:
     • Index 0 (1 $\le$ 2): Bloomed. Bouquet 1.
     • Index 2 (3 > 2): Not bloomed.
     • Index 4 (2 $\le$ 2): Bloomed. Bouquet 2.
   • Total Bouquets: 2. Target: 3.
   • Condition Failed. left = mid + 1 = 3.
6. Termination:
   • left is 3, right is 3. Loop ends.
   • Return 3.

Proof of Correctness

The algorithm relies on the monotonicity of the problem space. Let $f(d)$ be a boolean function that returns true if we can make $m$ bouquets on day $d$, and false otherwise.

• If $f(d)$ is true, then for any $d' > d$, $f(d')$ is also true because the set of bloomed flowers on day $d$ is a subset of bloomed flowers on day $d'$.
• This monotonicity guarantees that the first $d$ for which $f(d)$ is true is the global minimum.
• The greedy strategy within the check function (forming a bouquet as soon as we have $k$ adjacent flowers) is optimal because waiting or skipping a valid group of $k$ adjacent flowers never increases the total number of bouquets we can form later in the array; it only reduces the available "space" for subsequent bouquets.

Reference Implementation

C++ Solution for LeetCode 1482

cpp
class Solution {
public:
    int minDays(vector<int>& bloomDay, int m, int k) {
        // Use long long to prevent overflow for m * k
        long long val = (long long)m * k;
        if (val > bloomDay.size()) return -1;
        
        int left = INT_MAX, right = INT_MIN;
        for (int day : bloomDay) {
            left = min(left, day);
            right = max(right, day);
        }
        
        int ans = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (canMake(bloomDay, mid, m, k)) {
                ans = mid;
                right = mid - 1; // Try smaller days
            } else {
                left = mid + 1; // Need more days
            }
        }
        
        return ans;
    }
    
private:
    bool canMake(const vector<int>& bloomDay, int day, int m, int k) {
        int bouquets = 0;
        int adjacent_flowers = 0;
        
        for (int bloom : bloomDay) {
            if (bloom <= day) {
                adjacent_flowers++;
                if (adjacent_flowers == k) {
                    bouquets++;
                    adjacent_flowers = 0; // Reset after making a bouquet
                }
            } else {
                adjacent_flowers = 0; // Reset if adjacency is broken
            }
            
            if (bouquets >= m) return true;
        }
        
        return bouquets >= m;
    }
};

Java Solution for LeetCode 1482

java
class Solution {
    public int minDays(int[] bloomDay, int m, int k) {
        // Check feasibility using long to avoid overflow
        if ((long) m * k > bloomDay.length) {
            return -1;
        }
        
        int left = Integer.MAX_VALUE;
        int right = Integer.MIN_VALUE;
        
        for (int day : bloomDay) {
            left = Math.min(left, day);
            right = Math.max(right, day);
        }
        
        int ans = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (canMake(bloomDay, mid, m, k)) {
                ans = mid;
                right = mid - 1; // Try to minimize the days
            } else {
                left = mid + 1; // Increase days
            }
        }
        
        return ans;
    }
    
    private boolean canMake(int[] bloomDay, int day, int m, int k) {
        int bouquets = 0;
        int adjacentFlowers = 0;
        
        for (int bloom : bloomDay) {
            if (bloom <= day) {
                adjacentFlowers++;
                if (adjacentFlowers == k) {
                    bouquets++;
                    adjacentFlowers = 0;
                }
            } else {
                adjacentFlowers = 0;
            }
            
            if (bouquets >= m) return true;
        }
        
        return false;
    }
}

Python Solution for LeetCode 1482

python
class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m * k > len(bloomDay):
            return -1
            
        def can_make(day):
            bouquets = 0
            flowers = 0
            for bloom in bloomDay:
                if bloom <= day:
                    flowers += 1
                    if flowers == k:
                        bouquets += 1
                        flowers = 0
                else:
                    flowers = 0
                
                if bouquets >= m:
                    return True
            return False
            
        left, right = min(bloomDay), max(bloomDay)
        ans = -1
        
        while left <= right:
            mid = (left + right) // 2
            if can_make(mid):
                ans = mid
                right = mid - 1
            else:
                left = mid + 1
                
        return ans

Why does my solution TLE even with Binary Search? Ensure your canMake function is strictly $O(N)$. If you are using nested loops or sorting inside the check function, the complexity increases. Also, verify your binary search bounds. If you set right to a fixed constant like $10^9$ instead of max(bloomDay), it is still valid but slightly less efficient.

Why does the greedy approach work? Shouldn't I skip some flowers? No. This is a common conceptual gap. Because we need adjacent flowers, skipping a valid bloomed flower at index i to start a bouquet at i+1 never helps. It only reduces the contiguous segment available. Greedily completing a bouquet as soon as count reaches k is always optimal.

Why is my loop infinite? This usually happens due to incorrect binary search boundary updates. If you use left < right loop condition, ensure right = mid (not mid - 1) when the condition is met. If you use left <= right, ensure right = mid - 1 and left = mid + 1. The provided solutions use the left <= right template which is generally less error-prone for beginners.