Minimum Days to Make M Bouquets

Problem

Each position i blooms on day bloomDay[i]. A bouquet needs k adjacent bloomed flowers. Return the minimum number of days to make m bouquets, or -1 if impossible.

Constraints

• 1 ≤ bloomDay.length ≤ 10⁵
• 1 ≤ bloomDay[i] ≤ 10⁹
• 1 ≤ m, k ≤ bloomDay.length

Approach — Binary Search

This is a Binary Search problem. The idea: repeatedly halve the search space, discarding the half that can't contain the answer. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(log n) time.

Solution code

Python

class Solution:
    def minDays(self, bloomDay, m, k):
        if m * k > len(bloomDay):
            return -1
        def ok(day):
            bouquets = flowers = 0
            for b in bloomDay:
                if b <= day:
                    flowers += 1
                    if flowers == k:
                        bouquets += 1
                        flowers = 0
                else:
                    flowers = 0
            return bouquets >= m
        lo, hi = min(bloomDay), max(bloomDay)
        while lo < hi:
            mid = (lo + hi) // 2
            if ok(mid):
                hi = mid
            else:
                lo = mid + 1
        return lo

Java

class Solution {
    public int minDays(int[] bloomDay, int m, int k) {
        long need = (long) m * k;
        if (need > bloomDay.length) return -1;
        int lo = Integer.MAX_VALUE, hi = 0;
        for (int d : bloomDay) { lo = Math.min(lo, d); hi = Math.max(hi, d); }
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            int bouquets = 0, run = 0;
            for (int d : bloomDay) {
                if (d <= mid) {
                    run++;
                    if (run == k) { bouquets++; run = 0; }
                } else run = 0;
            }
            if (bouquets >= m) hi = mid;
            else               lo = mid + 1;
        }
        return lo;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.