Minimum Number of Days to Make m Bouquets

Medium
816.

Minimum Number of Days to Make m Bouquets

Minimum Number of Days to Make m Bouquets is a medium coding problem on arrays and binary search, asked in Amazon, Google, PhonePe and Swiggy interviews.

Flower i blooms on day bloomDay[i] and stays bloomed. One bouquet uses k adjacent bloomed flowers, and each flower can be used in at most one bouquet.

Return the earliest day on which m bouquets can be made, or -1 if it is impossible.

Example 1

Input
bloomDay = [1,10,3,10,2], m = 3, k = 1
Output
3
Explanation
By day 3 the flowers at 0, 2 and 4 have bloomed.

Example 2

Input
bloomDay = [1,10,3,10,2], m = 3, k = 2
Output
-1
Explanation
Only 5 flowers exist but 6 are needed.

Example 3

Input
bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
Output
12

Constraints

  • 1 <= bloomDay.length <= 100000
  • 1 <= bloomDay[i] <= 1000000000
  • 1 <= m <= 1000000
  • 1 <= k <= bloomDay.length
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} bloomDay
 * @param {number} m
 * @param {number} k
 * @return {number}
 */
var minDays = function(bloomDay, m, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Number of Days to Make m Bouquets — Solution

Minimum Number of Days to Make m Bouquets solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Number of Days to Make m Bouquets is a medium coding problem on arrays and binary search, asked in Amazon, Google, PhonePe and Swiggy interviews.

  • Difficulty: Medium
  • Topics: Arrays, Binary Search
  • Asked at: Amazon, Google, PhonePe, Swiggy
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Flower i blooms on day bloomDay[i] and stays bloomed. One bouquet uses k adjacent bloomed flowers, and each flower can be used in at most one bouquet.

Return the earliest day on which m bouquets can be made, or -1 if it is impossible.

Example 1

Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
Output: 3
Explanation: By day 3 the flowers at 0, 2 and 4 have bloomed.

Example 2

Input: bloomDay = [1,10,3,10,2], m = 3, k = 2
Output: -1
Explanation: Only 5 flowers exist but 6 are needed.

Example 3

Input: bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
Output: 12

Constraints

  • 1 <= bloomDay.length <= 100000
  • 1 <= bloomDay[i] <= 1000000000
  • 1 <= m <= 1000000
  • 1 <= k <= bloomDay.length

Hints for Minimum Number of Days to Make m Bouquets

  1. Hint 1

    Waiting longer never destroys a bouquet, so feasibility is monotone in the day.

  2. Hint 2

    Binary search the day; for a candidate, greedily cut bouquets from every run of bloomed flowers.

  3. Hint 3

    If m · k exceeds the number of flowers, no day can work.

How to solve Minimum Number of Days to Make m Bouquets

Binary search the answer. For a fixed day, the maximum number of bouquets is obtained greedily: walk the array and close a bouquet every time k consecutive bloomed flowers accumulate. That count only grows as the day advances.

Approach

  1. Reject outright when m · k > n.
  2. Set the search range to the minimum and maximum bloom days.
  3. can(day): count runs of flowers with bloomDay[i] <= day, taking floor(runLength / k) bouquets from each — the reset-on-k loop does exactly that.
  4. Binary search the smallest feasible day.

Why it works

Greedy cutting is optimal within a run of length L: any arrangement of adjacent groups of k inside it yields at most floor(L / k) bouquets, and cutting from the left achieves that. Since a later day only turns more flowers bloomed, runs can only lengthen and merge, so the bouquet count is non-decreasing — the predicate is monotone.

Complexity

  • Time — O(n log D) where D is the bloom-day range
  • Space — O(1)

Pitfalls

  • m · k reaches 10^6 · 10^5 = 10^11 — the impossibility check needs 64-bit arithmetic.
  • A run must reset on an unbloomed flower, otherwise non-adjacent flowers get combined.
  • Searching from day 1 rather than the minimum bloom day still works but wastes iterations.

Reference solution

Python

from typing import List

def minDays(bloomDay: List[int], m: int, k: int) -> int:
    n = len(bloomDay)
    if m * k > n:
        return -1
    lo, hi = min(bloomDay), max(bloomDay)

    def can(day: int) -> bool:
        made = run = 0
        for b in bloomDay:
            if b <= day:
                run += 1
                if run == k:
                    made += 1
                    run = 0
            else:
                run = 0
        return made >= m

    while lo < hi:
        mid = (lo + hi) // 2
        if can(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Java

private static boolean canBouquet(int[] bloomDay, int m, int k, int day) {
    int made = 0, run = 0;
    for (int b : bloomDay) {
        if (b <= day) {
            run++;
            if (run == k) {
                made++;
                run = 0;
            }
        } else {
            run = 0;
        }
    }
    return made >= m;
}

public static int minDays(int[] bloomDay, int m, int k) {
    int n = bloomDay.length;
    if ((long) m * k > n) return -1;
    int lo = bloomDay[0], hi = bloomDay[0];
    for (int b : bloomDay) {
        lo = Math.min(lo, b);
        hi = Math.max(hi, b);
    }
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canBouquet(bloomDay, m, k, mid)) hi = mid; else lo = mid + 1;
    }
    return lo;
}

C++

static bool canBouquet(vector<int>& bloomDay, int m, int k, int day) {
    int made = 0, run = 0;
    for (int b : bloomDay) {
        if (b <= day) {
            run++;
            if (run == k) {
                made++;
                run = 0;
            }
        } else {
            run = 0;
        }
    }
    return made >= m;
}

int minDays(vector<int>& bloomDay, int m, int k) {
    int n = (int) bloomDay.size();
    if ((long long) m * k > n) return -1;
    int lo = bloomDay[0], hi = bloomDay[0];
    for (int b : bloomDay) {
        lo = min(lo, b);
        hi = max(hi, b);
    }
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canBouquet(bloomDay, m, k, mid)) hi = mid; else lo = mid + 1;
    }
    return lo;
}

JavaScript

var minDays = function(bloomDay, m, k) {
    var n = bloomDay.length;
    if (m * k > n) return -1;
    var lo = bloomDay[0], hi = bloomDay[0], i;
    for (i = 1; i < n; i++) {
        if (bloomDay[i] < lo) lo = bloomDay[i];
        if (bloomDay[i] > hi) hi = bloomDay[i];
    }
    var can = function(day) {
        var made = 0, run = 0;
        for (var j = 0; j < n; j++) {
            if (bloomDay[j] <= day) {
                run++;
                if (run === k) { made++; run = 0; }
            } else run = 0;
        }
        return made >= m;
    };
    while (lo < hi) {
        var mid = Math.floor((lo + hi) / 2);
        if (can(mid)) hi = mid; else lo = mid + 1;
    }
    return lo;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search