Code Implementation

class Solution:
    def minDays(self, bloomDay, m, k):
        if m * k > len(bloomDay):
            return -1

        def canMake(days):
            bouquets = flowers = 0
            for bloom in bloomDay:
                if bloom <= days:
                    flowers += 1
                    if flowers == k:
                        bouquets += 1
                        flowers = 0
                else:
                    flowers = 0
            return bouquets >= m

        left, right = min(bloomDay), max(bloomDay)
        answer = -1
        while left <= right:
            mid = (left + right) // 2
            if canMake(mid):
                answer = mid
                right = mid - 1
            else:
                left = mid + 1
        return answer
      

class Solution {
public:
    int minDays(vector<int>& bloomDay, int m, int k) {
        if ((long long)m * k > bloomDay.size()) return -1;

        auto canMake = [&](int days) {
            int bouquets = 0, flowers = 0;
            for (int bloom : bloomDay) {
                if (bloom <= days) {
                    flowers++;
                    if (flowers == k) {
                        bouquets++;
                        flowers = 0;
                    }
                } else {
                    flowers = 0;
                }
            }
            return bouquets >= m;
        };

        int left = *min_element(bloomDay.begin(), bloomDay.end());
        int right = *max_element(bloomDay.begin(), bloomDay.end());
        int answer = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canMake(mid)) {
                answer = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return answer;
    }
};
      

class Solution {
    public int minDays(int[] bloomDay, int m, int k) {
        if ((long) m * k > bloomDay.length) return -1;

        int left = Integer.MAX_VALUE, right = Integer.MIN_VALUE;
        for (int bloom : bloomDay) {
            left = Math.min(left, bloom);
            right = Math.max(right, bloom);
        }
        int answer = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canMake(bloomDay, m, k, mid)) {
                answer = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return answer;
    }

    private boolean canMake(int[] bloomDay, int m, int k, int days) {
        int bouquets = 0, flowers = 0;
        for (int bloom : bloomDay) {
            if (bloom <= days) {
                flowers++;
                if (flowers == k) {
                    bouquets++;
                    flowers = 0;
                }
            } else {
                flowers = 0;
            }
        }
        return bouquets >= m;
    }
}
      

var minDays = function(bloomDay, m, k) {
    if (m * k > bloomDay.length) return -1;

    function canMake(days) {
        let bouquets = 0, flowers = 0;
        for (let bloom of bloomDay) {
            if (bloom <= days) {
                flowers++;
                if (flowers === k) {
                    bouquets++;
                    flowers = 0;
                }
            } else {
                flowers = 0;
            }
        }
        return bouquets >= m;
    }

    let left = Math.min(...bloomDay), right = Math.max(...bloomDay);
    let answer = -1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (canMake(mid)) {
            answer = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return answer;
};
      

Problem Description

You are given an array bloomDay, where bloomDay[i] is the day the i-th flower will bloom. You are also given two integers: m and k. Your task is to make m bouquets, each consisting of k adjacent flowers. You cannot reuse any flower in more than one bouquet.

Return the minimum number of days needed until you can make m bouquets. If it is impossible, return -1.

• Each bouquet must contain exactly k adjacent flowers.
• You cannot use the same flower in more than one bouquet.
• There is always one valid answer or you must return -1 if it is not possible.

Thought Process

At first glance, the problem seems to ask for checking every possible day, seeing if enough bouquets can be made, and picking the smallest such day. A brute-force approach would be to simulate each possible day from the earliest to the latest bloom, and for each, try to make bouquets by walking through the array.

However, this would be too slow for large arrays, as the number of days can be huge. We need a more efficient way to home in on the answer. The key insight is that if you can make m bouquets on a certain day, you can definitely do it on any later day, since more flowers will have bloomed. This property suggests a binary search approach.

By thinking in terms of "the earliest day when making bouquets is possible," we can efficiently search for the answer instead of checking every day one by one.

Solution Approach

• Step 1: Check for Impossibility
  If m * k > len(bloomDay), it's impossible to make m bouquets, since there aren't enough flowers.
• Step 2: Binary Search on Days
  Set your search range between the earliest and latest bloom day in bloomDay. For each day in this range (using binary search), check if it's possible to make m bouquets by that day.
• Step 3: Feasibility Function
  For a given day, walk through bloomDay:
  • Keep a counter for consecutive bloomed flowers (those with bloomDay[i] <= day).
  • When you reach k consecutive bloomed flowers, count one bouquet and reset the counter.
  • If you reach m bouquets, return True.
  • If not enough bouquets are made after checking all flowers, return False.
• Step 4: Binary Search Loop
  If you can make m bouquets on day mid, try for an earlier day (right = mid - 1), otherwise try a later day (left = mid + 1).
• Step 5: Return the Answer
  The answer is the smallest day for which the feasibility function returns True. If no such day exists, return -1.

This approach is efficient because binary search reduces the number of days to check, and the feasibility function checks each flower only once per candidate day.

Example Walkthrough

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

• Step 1: Minimum day = 1, Maximum day = 10.
• Binary Search:
  • mid = 5: Can we make 3 bouquets by day 5?
    Flowers bloomed by day 5: [1, 3, 2] (positions 0, 2, 4). Each is a single flower, and k=1, so each can be a bouquet. We can make 3 bouquets → Try for earlier day.
  • mid = 3: Can we make 3 bouquets by day 3?
    Flowers bloomed: [1, 3] (positions 0, 2), only 2 bouquets possible → Not enough. Try later day.
  • mid = 4: Only [1, 3] have bloomed, still only 2 bouquets → Not enough.
  • mid = 5: Already checked, so the answer is 5.
• Final Answer: 3 bouquets can be made earliest on day 5.

Time and Space Complexity

• Brute-force Approach:
  For each possible day (up to max(bloomDay)), check if m bouquets can be made. Each check is O(n), and there could be up to 10^9 days, so total is O(n * max(bloomDay)) — far too slow.
• Optimized (Binary Search) Approach:
  Binary search over days takes O(log(max(bloomDay))). For each candidate day, we scan the array once (O(n)). So total time is O(n * log(max(bloomDay))).
• Space Complexity:
  O(1) extra space, since we only use a few variables for counters. No extra data structures are needed.

Summary

The key to this problem is recognizing that the question "Can we make m bouquets by day X?" is monotonic: if it's possible for day X, it's also possible for any day after X. This allows us to use binary search to efficiently find the minimum day. The feasibility check is simple and fast, and the overall approach is both elegant and practical for large input sizes.