Crack the Backend

Problem Statement

You have n flowers; flower i blooms on day bloomDay[i]. You need to make m bouquets. To make one bouquet you need k adjacent flowers that have all bloomed. Return the minimum number of days you need to wait so that you can make at least m bouquets. If it is impossible (e.g. n < m * k), return -1.

On day d, a flower i is bloomed if bloomDay[i] <= d. We can only use adjacent bloomed flowers to form a bouquet (each bouquet uses k consecutive bloomed flowers). We want the smallest d such that we can form m such bouquets.
Binary search on d: For a candidate day mid, count how many bouquets we can make (scan for contiguous bloomed segments of length >= k, each segment contributes segmentLen / k bouquets). If count >= m, we can try a smaller day (high = mid); else low = mid + 1.

Key Observations

For day d, flowers with bloomDay[i] <= d are bloomed. We need contiguous segments of bloomed flowers; each segment of length L gives L / k bouquets (integer division). Total bouquets = sum over segments of (segment length / k). If total >= m, day d works.
Binary search d in [min(bloomDay), max(bloomDay)] (or [1, max]). If m * k > n, return -1.

Approach

High-level: If m * k > bloomDay.length return -1. Binary search day in [min(bloomDay), max(bloomDay)]. For each mid, count bouquets: scan array, when bloomDay[i] <= mid count contiguous bloomed length; when we have >= k contiguous, add length/k bouquets. If count >= m, high = mid; else low = mid + 1. Return low.

Steps:

If (long) m * k > bloomDay.length return -1. low = min(bloomDay), high = max(bloomDay). While low < high: mid = low + (high - low) / 2. Count bouquets at day mid (contiguous bloomed segments, each segment contributes len/k). If count >= m, high = mid; else low = mid + 1.
Return low.

Implementation

Java

public int minDays(int[] bloomDay, int m, int k) {

    if ((long) m * k > bloomDay.length) {
        return -1;
    }

    int low = 1, high = (int) 1e9;

    while (low < high) {
        int mid = low + (high - low) / 2;
        int bouquets = 0, streak = 0;

        for (int d : bloomDay) {
            streak = d <= mid ? streak + 1 : 0;

            if (streak == k) { bouquets++; streak = 0; }
        }

        if (bouquets >= m) {
            high = mid;
        }
        else {
            low = mid + 1;
        }
    }

    return low;
}

Test Cases

Example 1

Input

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

Expected

3

Explanation

Day 3: all bloomed, 3 bouquets of 1.

Complexity Analysis

Time: O(n log(max(bloomDay))).
Space: O(1).

Follow-ups

Similar: minimum time to complete with contiguous segments.