Course4all
Join us on telegram
Home/dsa/Binary Search/Minimum Number of Days to Make m Bouquets

Minimum Number of Days to Make m Bouquets

Master this topic with zero to advance depth.

Minimum Number of Days to Make m Bouquets

Return the minimum number of days DD such that you can make mm bouquets using kk adjacent flowers each. Each bouquet must consist of kk adjacent flowers.

Medium

Examples

Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
Output: 3
Approach 1

Level I: Brute Force (Iterate Days)

Intuition

Try every possible day from min(bloomDay)\\min(bloomDay) to max(bloomDay)\\max(bloomDay). For each day, check if it's possible to form mm bouquets.

⏱ $O(Range \\cdot N)$💾 $O(1)$

Detailed Dry Run

bloomDay = [1,10,3,10,2], m=3, k=1. Sorted unique days: [1,2,3,10]. Day 1: 1 bouquet. Day 2: 2 bouquets. Day 3: 3 bouquets. Return 3.

java
class Solution {
    public int minDays(int[] bloomDay, int m, int k) {
        if ((long)m * k > bloomDay.length) return -1;
        int maxD = 0; for (int d : bloomDay) maxD = Math.max(maxD, d);
        for (int d = 1; d <= maxD; d++) {
            if (canMake(bloomDay, m, k, d)) return d;
        }
        return -1;
    }
    boolean canMake(int[] bloomDay, int m, int k, int d) {
        int count = 0, bouquets = 0;
        for (int b : bloomDay) {
            if (b <= d) { if (++count == k) { bouquets++; count = 0; } } else count = 0;
        }
        return bouquets >= m;
    }
}
Approach 2

Level II: Optimal (Optimization with Sorted Days)

Intuition

Instead of checking every day from 1 to maxD, only check days where at least one flower blooms. These are the unique values in bloomDay.

⏱ $O(N \\log N + N \\cdot \\text{UniqueDays})$💾 $O(N)$

Detailed Dry Run

bloomDay = [1,10,3,10,2], m=3, k=1. Unique days sorted: [1, 2, 3, 10]. Check 1: 1 (fail), 2: 2 (fail), 3: 3 (pass). Result 3.

java
class Solution {
    public int minDays(int[] bloomDay, int m, int k) {
        if ((long)m * k > bloomDay.length) return -1;
        int[] sortedDays = Arrays.stream(bloomDay).distinct().sorted().toArray();
        for (int d : sortedDays) {
            if (canMake(bloomDay, m, k, d)) return d;
        }
        return -1;
    }
    boolean canMake(int[] bloomDay, int m, int k, int d) {
        int count = 0, bouquets = 0;
        for (int b : bloomDay) {
            if (b <= d) { if (++count == k) { bouquets++; count = 0; } } else count = 0;
        }
        return bouquets >= m;
    }
}
Approach 3

Level III: Optimal (Binary Search on Answer)

Intuition

The number of bouquets possible is a monotonic function of days. We can binary search the result in the range [min(bloomDay),max(bloomDay)][\\min(bloomDay), \\max(bloomDay)].

⏱ $O(N \\log(Max - Min))$💾 $O(1)$

Detailed Dry Run

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

  • Mid 5: [B, No, B, No, B] -> 3 bouquets. OK, R=5.
  • Mid 2: [B, No, No, No, B] -> 2 bouquets. Too few, L=3.
  • Mid 3: [B, No, B, No, B] -> 3 bouquets. OK, R=3. Result: 3.
java
class Solution {
    public int minDays(int[] bloomDay, int m, int k) {
        if ((long)m * k > bloomDay.length) return -1;
        int l = 1, r = 1000000000;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (canMake(bloomDay, m, k, mid)) r = mid; else l = mid + 1;
        }
        return l;
    }
    boolean canMake(int[] bloomDay, int m, int k, int d) {
        int count = 0, bouq = 0;
        for (int b : bloomDay) {
            if (b <= d) { if (++count == k) { bouq++; count = 0; } } else count = 0;
        }
        return bouq >= m;
    }
}
← Previous QuestionSwim in Rising Water
Next Question →Find the Smallest Divisor Given a Threshold