Problem Overview

Given an array bloomDay where bloomDay[i] represents the day on which the i-th flower blooms, determine the minimum number of days required to make m bouquets. Each bouquet requires exactly k adjacent flowers that have already bloomed.

If it's impossible to create m bouquets (insufficient flowers), return -1.

Constraints

• 1 <= bloomDay.length <= 10^5
• 1 <= bloomDay[i] <= 10^9
• 1 <= m <= 10^6
• 1 <= k <= n

Solution Strategy

The problem can be solved efficiently using binary search combined with a greedy validation function.

Key Observations

1. If m * k > n, it's mathematically impossible to create m bouquets
2. The answer lies between the minimum and maximum bloom days
3. For a given day d, we can greedily check if m bouquets can be formed

Greedy Validation Functon

When checking if m bouquets are possible by day d:

• Iterate through the flower array
• Track the last index where a flower was unavailable (lastUnavailable)
• When a flower is available, check if the distance from current index to lastUnavailable is atleast k
• If yes, we can form one bouquet and reset the last unavailable position

This approach efficiently counts consecutive blooming flowers using the gap tracking technique.

Binary Search Implementation

/**
 * @param {number[]} bloomDay
 * @param {number} bouquetsNeeded
 * @param {number} flowersPerBouquet
 * @return {number}
 */
var minDays = function(bloomDay, bouquetsNeeded, flowersPerBouquet) {
    const totalFlowers = bouquetsNeeded * flowersPerBouquet;
    if (totalFlowers > bloomDay.length) {
        return -1;
    }
    
    const canFormBouquets = (day) => {
        let remaining = bouquetsNeeded;
        let gapEnd = -1;
        
        for (let i = 0; i < bloomDay.length; i++) {
            if (bloomDay[i] <= day) {
                // Current flower is available
                if (i - gapEnd >= flowersPerBouquet) {
                    remaining--;
                    if (remaining === 0) {
                        return true;
                    }
                    gapEnd = i;
                }
            } else {
                // Current flower not yet bloomed, update gap boundary
                gapEnd = i;
            }
        }
        return false;
    };
    
    let left = 1;
    let right = Math.max(...bloomDay);
    let result = -1;
    
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        
        if (canFormBouquets(mid)) {
            result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return result;
};

Complexity Analysis

• Time Complexity: O(n log D) where n is the number of flowers and D is the range of bloom days
• Space Complexity: O(1) excluding input storage

How the Gap Tracking Works

Consider bloomDay = [7,7,7,7,12,7,7], bouquetsNeeded = 2, flowersPerBouquet = 3:

At day 7:

• Indices 0,1,2,3,5,6 are available
• Using gap tracking: the first valid group of 3 consecutive available flowers forms the first bouquet
• After forming a bouquet at index 2, the gap resets to index 2
• No second group of 3 consecutive available flowers exists within the remaining sequence

At day 12:

• All flowers are available
• Gap tracking identifies two separate groups of 3 consecutive flowers
• Both bouquets can be formed

The gap tracking method avoids nested loops by simply remembering the last position where the consecutive sequence was broken, making each check run in linear time.