Minimum days to make M bouquets

Intuition

Binary search on number of days. At d days, count bouquets possible = sum of floor(consecutive_bloomed / k). Find minimum d.

Algorithm

1lo=min(bloomDay), hi=max(bloomDay).
2Feasibility(d): count bouquets. If >= m: feasible.

Common Pitfalls

•If n < m*k: impossible, return -1. Reset streak when flower not yet bloomed.

Minimum days to make M bouquets.java

Java

// Approach: Binary search on days. For a given day, count consecutive bloomed flowers of length k.
// Time: O(n log(max)) Space: O(1)
class Solution {
    public int minDaysBloom(int[] arr, int k, int m) {
        int n = arr.length;

        if ((long) m * k > n)
            return -1;

        int left = Integer.MAX_VALUE, right = Integer.MIN_VALUE;

        for (int day : arr) {
            left = Math.min(left, day);
            right = Math.max(right, day);
        }

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canMakeBouquets(arr, m, k, mid))
                right = mid;
            else
                left = mid + 1;
        }

        return left;
    }

    private boolean canMakeBouquets(int[] arr, int m, int k, int day) {
        int count = 0, bouquets = 0;
        for (int bloomDay : arr) {
            if (bloomDay <= day) {
                count++;
                if (count == k) {
                    bouquets++;
                    count = 0;
                }
            } else
                count = 0;
        }
        return bouquets >= m;
    }
}

Was this solution helpful?