☕ DSA Java Articles

Topics › Binary Search › BS on Answers

Minimum days to make M bouquets

Medium TUF ID 95 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

A garden has n flowers in a row; flower i blooms on day bloomDay[i] and stays bloomed afterwards. You want to make m bouquets, and each bouquet needs exactly k flowers that are adjacent in the row. A flower can be used in at most one bouquet. Return the minimum number of days you must wait until it is possible to make all m bouquets. If it is impossible, return -1.

Constraints: 1 ≤ n ≤ 10^5, 1 ≤ bloomDay[i] ≤ 10^9, 1 ≤ m ≤ 10^6, 1 ≤ k ≤ n.

Example 1

bloomDay = [1, 10, 3, 10, 2], m = 3, k = 1
answer = 3          // after day 3 the flowers at indices 0, 2, 4 have bloomed: three bouquets of one flower

Example 2

bloomDay = [7, 7, 7, 7, 12, 7, 7], m = 2, k = 3
answer = 12         // on day 7 the row is [x x x x _ x x]: only one run of 3, so we must wait for day 12

Example 3

bloomDay = [1, 10, 3, 10, 2], m = 3, k = 2
answer = -1         // 3 bouquets of 2 need 6 flowers, but there are only 5

The feasibility check

For a fixed waiting time day, flower i is available if bloomDay[i] ≤ day. The bouquets need adjacent flowers, so we scan the row and count maximal runs of available flowers. A run of length L yields floor(L / k) bouquets. The simplest way to implement that is a counter run that increases on each available flower, is reset to 0 on an unavailable one, and every time it reaches k we bank one bouquet and reset it. Cutting a bouquet as soon as k consecutive flowers are available is optimal: within a run, where exactly we cut does not change how many groups of k fit.

static boolean possible(int[] bloom, int day, int m, int k) {
    int bouquets = 0, run = 0;
    for (int b : bloom) {
        if (b <= day) {
            run++;
            if (run == k) { bouquets++; run = 0; }
        } else {
            run = 0;
        }
    }
    return bouquets >= m;
}

This runs in O(n) and is shared by both approaches.

Impossibility up front

We need m * k distinct flowers. If m * k > n there is no answer on any day, so both methods return -1 before searching. Note the multiplication: m and k can each be up to 10^6 and 10^5, so m * k is computed as a long. In int arithmetic 10^6 * 10^6 would wrap and the check could silently pass.

Approach 1: Brute force, try every day

Intuition. Nothing changes between bloom days, so only the values that appear in bloomDay matter, and in particular the answer lies between min(bloomDay) and max(bloomDay). Waiting longer never hurts (more flowers available, same adjacency), so the first day in that range on which possible succeeds is the answer.

Algorithm.

  1. If m * k > n, return -1.
  2. Compute min and max of bloomDay.
  3. For day = min, min + 1, ..., max: if possible(bloom, day, m, k), return day.
  4. Return -1 (not reached when step 1 passed, because on day max every flower is available).
static int bruteForce(int[] bloom, int m, int k) {
    int n = bloom.length;
    if ((long) m * k > n) return -1;
    int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
    for (int b : bloom) { min = Math.min(min, b); max = Math.max(max, b); }
    for (int day = min; day <= max; day++) {
        if (possible(bloom, day, m, k)) return day;
    }
    return -1;
}

Complexity. Time O(n * (max - min)): up to 10^9 days, each an O(n) scan. Space O(1). Far too slow when the bloom days are spread out, but correct.

A slightly smarter brute force would only test the distinct values in bloomDay (sorted), which is O(n^2) in the worst case. Still too slow for n = 10^5.

Approach 2: Optimal, binary search on the day

Intuition. possible(day) is monotonic: if we can make the bouquets on day d, we can also make them on any later day, because the set of available flowers only grows and the same cuts remain valid. Over day = min, ..., max the predicate therefore looks like F F F ... T T T, and the answer is the first T. Binary search it: on a feasible mid record it and look earlier; on an infeasible mid look later.

Algorithm.

  1. If m * k > n, return -1.
  2. Compute min and max; set lo = min, hi = max, ans = max.
  3. While lo ≤ hi:
    • mid = lo + (hi - lo) / 2.
    • If possible(bloom, mid, m, k): ans = mid, hi = mid - 1.
    • Else: lo = mid + 1.
  4. Return ans.
static int optimal(int[] bloom, int m, int k) {
    int n = bloom.length;
    if ((long) m * k > n) return -1;
    int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
    for (int b : bloom) { min = Math.min(min, b); max = Math.max(max, b); }
    int lo = min, hi = max, ans = max;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (possible(bloom, mid, m, k)) { ans = mid; hi = mid - 1; }
        else lo = mid + 1;
    }
    return ans;
}

Dry run on bloomDay = [7, 7, 7, 7, 12, 7, 7], m = 2, k = 3:

lo hi mid available pattern bouquets possible? ans next
7 12 9 x x x x _ x x 1 no 12 [10, 12]
10 12 11 x x x x _ x x 1 no 12 [12, 12]
12 12 12 x x x x x x x 2 yes 12 [12, 11] stop

Result 12. On the full row of 7 available flowers the counter banks a bouquet at positions 3 and 6, giving 2.

Complexity. Time O(n log(max - min)): at most about 30 iterations of an O(n) scan. Space O(1).

Why ans = max as the initial value? When m * k ≤ n, on day max every flower is available, so the row is one run of length n ≥ m * k and possible is true. The fallback is therefore always a valid answer, and the search only improves on it.

Edge cases and pitfalls