Minimum Days to Make M Bouquets, thesarfo

n roses, arr[i] = day rose i blooms. Need k adjacent bloomed roses per bouquet, m bouquets total. Find the minimum day by which m bouquets are possible, or -1. (LeetCode problem)

Impossible case: if m * k > n, there simply aren’t enough roses — return -1 immediately.

Feasibility check: for a candidate day, scan the array counting consecutive already-bloomed roses (arr[i] <= day); every run of k consecutive bloomed roses forms a bouquet (count / k, with the counter resetting on an unbloomed rose).

boolean possible(int[] arr, int day, int m, int k) {
    int count = 0;
    int numOfBouquets = 0;

    for (int i = 0; i < arr.length; i++) {
        if (arr[i] <= day) {
            count++;
        } else {
            numOfBouquets += count / k;
            count = 0;
        }
    }

    numOfBouquets += count / k;

    return numOfBouquets >= m;
}

Brute force: try every day from min(arr) to max(arr), returning the first that’s possible.

Optimal — binary search: if a day doesn’t work, no earlier day will either (bouquets only get harder with less time), so the “possible” days form a contiguous suffix of [min(arr), max(arr)] — exactly the shape binary search wants.

public int minDays(int[] arr, int m, int k) {
    int n = arr.length;

    long val = (long) m * k;
    if (val > n) {
        return -1;
    }

    int left = Integer.MAX_VALUE;
    int right = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        left = Math.min(left, arr[i]);
        right = Math.max(right, arr[i]);
    }

    while (left <= right) {
        int mid = (left + right) / 2;

        if (possible(arr, mid, m, k)) {
            right = mid; // try to find an earlier possible day
        } else {
            left = mid + 1; // need a later day
        }
    }
    return left;
}