DSA sheet · Binary Search · Binary search on answer

Minimum Number of Days to Make m Bouquets

Another binary search on answer problem. This time the answer is a number of days to wait. The new ideas the teacher brings in are: a quick base case that tells us right away when it's impossible (not enough flowers in total), the adjacent flowers rule, which forces us to throw away our partly-collected flowers whenever we hit one that hasn't bloomed, and choosing low = min(bloomDay) and high = max(bloomDay). She ends the video with the pattern's two-line summary, which is worth memorising.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Brute force: try every day from min to max
• Part B · Optimal: binary search on the day
• Part C · Revision page

Part 0 · Before starting

Why binary search works at all

Binary search only needs a yes/no question that switches once along an ordered set of values: no, no, no, then yes, yes, yes. Such a question is called monotonic. Looking at the middle value tells us which side the switch is on, and we throw away the other side. The values can be an array, or a range of numbers we choose, which is what this pattern does.

low, high, mid

• low / high: the two ends of the part we are still searching.
• mid: the middle value, the one we test.
• while low <= high: keep going until the two ends cross, so the very last value is tested too.

Why mid = low + (high - low) // 2?

Here days go up to 10⁹. In Java/C++, low + high could then reach 2 × 10⁹, which is past the int limit (about 2.1 × 10⁹ is the edge), and it would overflow into a wrong negative number. low + (high - low) / 2 never builds a number bigger than high. Python's ints never overflow, so in Python both forms are fine; we keep the safe one out of habit.

The pattern: binary search on answer

1. Answer range: the earliest day that could possibly work (low) and a day that surely works if anything does (high).
2. Check function: check(day) = "if I come on this day, can I make m bouquets?"
3. Monotonic: a flower that has bloomed stays bloomed. Waiting longer only adds bloomed flowers, never removes any. So once some day works, every later day works too: no no no yes yes yes.
4. Which side to keep: we want the minimum waiting = the first yes. Yes at mid → save it, go left. No → go right.

days:       low ........................................ high
check(day): no   no   no   no  YES  YES  YES  YES  YES
                               ^
                  the first YES = fewest days to wait

Part A · Brute force: try every day from min to max

LeetCode 1482

1The question in simple words

A garden has n flowers in a row. bloomDay[i] is the day flower i blooms. You can only pick a flower on or after its bloom day. If a flower says 10 and you come on day 7, 8 or 9, you can't pick it; you have to wait until day 10.

You want m bouquets. Each bouquet needs exactly k flowers that are adjacent (next to each other in the row, with no gap). Each flower can be in only one bouquet. Return the minimum number of days you must wait to be able to make m bouquets, or −1 if it's impossible.

On day 3, flowers 0 (bloomed day 1), 2 (day 3) and 4 (day 2) are open. k = 1, so each one alone is a bouquet → 3 bouquets ✓. On day 2 only flowers 0 and 4 are open → 2 bouquets, not enough.

2What the constraints tell us

• 1 <= n <= 10⁵ → at least one flower.
• 1 <= bloomDay[i] <= 10⁹ → fits an int, but the range of days is up to 10⁹ long.
• 1 <= m <= 10⁶, 1 <= k <= n → m × k can be 10⁶ × 10⁵ = 10¹¹, more than an int can hold. In Java she casts to long before multiplying. Python ints have no limit, so m * k is fine as it is.

3Intuition

The question wants a day. So, as with every problem of this pattern, we guess a day, then walk along the garden and count how many bouquets we could make if we came that day. Try days from the earliest upward; the first day that gives at least m bouquets is the fewest days to wait.

4Building the logic from examples

First: the base case (impossible no matter how long you wait)

The teacher changes the example to m = 3 bouquets of k = 2 flowers. That needs 3 × 2 = 6 flowers, but the garden only has 5. Even if we wait until every flower blooms, there aren't enough flowers. So:

The check: how many bouquets can I make on a given day?

Walk the garden left to right with two counters: count = adjacent open flowers collected so far for the current bouquet, and bouquets = bouquets made.

• Flower is open (bloomDay[i] <= day): pick it, count += 1. Why <=? If the flower bloomed on day 1 and we come on day 2, it's still there for us. Coming later is fine.
• We have k flowers (count == k): that's a bouquet, bouquets += 1. Then reset count = 0, otherwise the next flowers would be counted into the bouquet we just finished.
• Flower is not open yet: we can't pick it, and it breaks the chain. The flowers collected before it can't be joined with flowers after it (not adjacent). So throw them away: count = 0.
• At the end: possible if bouquets >= m.

The teacher walks this on [1, 10, 3, 10, 2], k = 1, day = 1: flower 0 (1 ≤ 1) → count 1 = k → bouquet 1, count 0. Flower 1 (10 > 1) → can't pick, move on. Flower 2 (3 > 1) → no. Flower 3 (10) → no. Flower 4 (2 > 1, it blooms tomorrow) → no. Only 1 bouquet < 3 → day 1 fails, try later days.

Choosing low and high

• low = min(bloomDay). Before the earliest bloom day, not a single flower is open, so it's pointless to try. In her example the earliest is day 1. If the garden's earliest bloom were day 5, trying days 1–4 would be a waste.
• high = max(bloomDay). On that day every flower is open. Waiting until day 11, 12, 13… can't open anything new, and we want the least waiting. So never go past it. In her example that's day 10.

5Approach steps

1. If m * k > n → return −1.
2. low = min(bloomDay), high = max(bloomDay).
3. For each day d from low to high: if canMake(d) → return d (the first that works is the minimum).
4. canMake(d): count = 0, bouquets = 0. For each flower: open → count += 1, and if count == k → bouquets += 1, count = 0. Not open → count = 0. Return bouquets ≥ m.
5. After the loop → return −1 (never reached once the base case passes).

6Code (Python)

class Solution:
    def minDays(self, bloomDay, m, k):
        n = len(bloomDay)
        if m * k > n:                       # not enough flowers at all
            return -1
        low = min(bloomDay)                  # nothing opens before this
        high = max(bloomDay)                 # everything is open by now
        for d in range(low, high + 1):
            if self.canMake(bloomDay, m, k, d):
                return d                     # first that works = minimum
        return -1

    def canMake(self, bloomDay, m, k, day):
        count = 0                            # adjacent open flowers in hand
        bouquets = 0
        for bloom in bloomDay:
            if bloom <= day:                 # open: pick it
                count += 1
                if count == k:               # enough for one bouquet
                    bouquets += 1
                    count = 0                # start the next bouquet fresh
            else:                            # not open: chain is broken
                count = 0
        return bouquets >= m

7Code line by line

8Dry run

bloomDay = [1, 10, 3, 10, 2], m = 3, k = 1. Base case: 3 × 1 = 3 ≤ 5 ✓. low = 1, high = 10.

day        :  1    2    3    4    5    6    7    8    9   10
bouquets   :  1    2    3    3    3    3    3    3    3    5
>= 3 ?     :  no   no  YES  YES  YES  YES  YES  YES  YES  YES
                        ^ first YES = 3

9Complexity & remember

• Outer loop: up to max − min ≈ 10⁹ days. Inner loop (canMake): all n ≤ 10⁵ flowers. Together ≈ 10¹⁴ → TLE (she submits it and gets TLE).
• The inner 10⁵ can't be avoided: every flower must be looked at to count bouquets. The outer loop is the one to speed up.
• Space O(1).

Part B · Optimal: binary search on the day

1The question

Same as Part A, same base case, same range, same canMake. As she puts it, nothing else changes: the for loop becomes a while loop with binary search.

2Constraints

The range min … max can be up to 10⁹ long. Halving it takes about log₂(10⁹) ≈ 30 steps.

3Intuition

The days low … high sit on a number line in sorted order, and "can I make m bouquets by this day?" switches from no to yes just once. So rather than walking every day, check the middle day and drop half the line.

4Building the decisions

• canMake(mid) is True: m bouquets are possible within mid days. Mid may be the answer, and going left we might not find anything better, so save it: ans = mid. Then try fewer days: high = mid - 1.
• canMake(mid) is False: mid isn't the answer, and fewer days won't help. Wait longer: low = mid + 1.
• ans starts at −1. If it were never updated, −1 would come back on its own (though, as shown above, once the base case passes some day always works).

She moves fast here because this is the same template as the previous problems of this pattern (Koko, Ship Packages, Min Speed). If it feels quick, revisit the first two.

5Approach steps

1. If m * k > n → −1.
2. low = min(bloomDay), high = max(bloomDay), ans = -1.
3. While low ≤ high: mid = low + (high − low) // 2.
4. canMake(mid) → ans = mid, high = mid − 1. Else → low = mid + 1.
5. Return ans.

6Code (Python)

class Solution:
    def minDays(self, bloomDay, m, k):
        n = len(bloomDay)
        if m * k > n:
            return -1
        low = min(bloomDay)
        high = max(bloomDay)
        ans = -1
        while low <= high:
            mid = low + (high - low) // 2       # mid = the day we test
            if self.canMake(bloomDay, m, k, mid):
                ans = mid                       # possible: remember it
                high = mid - 1                  # try waiting less
            else:
                low = mid + 1                   # not yet: wait longer
        return ans

    def canMake(self, bloomDay, m, k, day):
        count = 0
        bouquets = 0
        for bloom in bloomDay:
            if bloom <= day:
                count += 1
                if count == k:
                    bouquets += 1
                    count = 0
            else:
                count = 0
        return bouquets >= m

7Code line by line

8Dry run (hand tables)

Run 1: bloomDay = [1, 10, 3, 10, 2], m = 3, k = 1. low = 1, high = 10.

Run 2 (shows the adjacency reset): bloomDay = [7, 7, 7, 7, 12, 7, 7], m = 2, k = 3. Base case: 6 ≤ 7 ✓. low = 7, high = 12.

The circled 12 is where the chain breaks: before it we held 1 flower, after it we start again from 0. That's exactly the else: count = 0 line.

9Complexity & remember

• Time O(n × log(max − min)) ≈ 10⁵ × 30 = 3 × 10⁶ → passes. (Finding min and max is one extra O(n) pass.)
• Space O(1).

Part C · Revision page

s = Solution()
print(s.minDays([1, 10, 3, 10, 2], 3, 1))          # 3
print(s.minDays([1, 10, 3, 10, 2], 3, 2))          # -1  (needs 6 flowers, has 5)
print(s.minDays([7, 7, 7, 7, 12, 7, 7], 2, 3))     # 12
print(s.minDays([1000000000, 1000000000], 1, 1))   # 1000000000
print(s.minDays([1, 10, 2, 9, 3, 8, 4, 7, 5, 6], 4, 2))   # 9

Based on this video: Minimum Number of Days to Make m Bouquets | Binary Search on Answer