In the wild · git bisect: To find the commit that broke a build, git halves the range of commits on every test, so even 1,000 commits take about 10 checks.

About this problem

Cut a sorted search space in half each step. Also used on answer ranges, not only arrays.

Read the full statement and examples on LeetCode, try it for 20–30 minutes, then come back for the walkthrough.

Examples

Full statement on LeetCode ↗

Example 1
Duplicates
Input
bloomDay = [1, 10, 3, 10, 2]m = 3k = 1
Output
3
Example 2
DuplicatesNo valid answer
Input
bloomDay = [1, 10, 3, 10, 2]m = 3k = 2
Output
-1
Example 3
Duplicates
Input
bloomDay = [7, 7, 7, 7, 12, 7, 7]m = 2k = 3
Output
12

Code it here

Tab indents · ⌘/Ctrl+Enter runs · Esc leaves the editor

Step 6

Get it accepted

All test cases pass

Step 7

Review it so it sticks

Re-solve from memory after

The step that matters most: without reviews most of a solved problem fades within weeks. Three short re-solves, each just as you start to forget, are what make it yours.

Your notes

Three lines in your own words. They come back with this problem's reviews, so you can check yourself after recalling the solution.

Solve it yourself before you look

Reading the solution first feels like progress, but it makes the next similar problem — and the interview version — much harder, because you skipped the part where you figure it out. Give it an honest 20–30 minutes. Stuck? Re-read the pattern, watch the concept video, or try the brute force first.

Hidden: optimal solution

Stuck? One hint at a time.

or find it yourself with the pattern finder

Solution code

Optimal solution

Time O(n log(max day))Space O(1)

If m·k is more than the flowers, it's impossible. Otherwise on the day: by day d, walk the flowers counting runs of bloomed ones, each run of k making a bouquet. Find the first day that makes at least m.

class Solution:
    def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
        if m * k > len(bloomDay):
            return -1

        def bouquets(day: int) -> int:
            made = run = 0
            for d in bloomDay:
                run = run + 1 if d <= day else 0
                if run == k:
                    made += 1
                    run = 0
            return made

        lo, hi = min(bloomDay), max(bloomDay)
        while lo < hi:
            mid = (lo + hi) // 2
            if bouquets(mid) >= m:
                hi = mid
            else:
                lo = mid + 1
        return lo

Reference solution, tested in Python, Java and C++.

Other ways to solve it

Thought of another approach (slower, or cleverer)? Code it here: the same tests check any approach.
Community solutions on LeetCode ↗ for many more versions, in many languages. Read them after you've solved it.

Srujan's notes aren't here yet. When he solves this one in his journal, his own writeup and solutions show up on this page too.

Examples

Example 1

Example 2

Example 3

Code it here

Your notes

Solve it yourself before you look

Solution code