Workspace

Problem workspace

3 day streakD

Minimum Days to Make Bouquets

MediumBinary SearchSearch on the answer

The challenge

Find the earliest day when m bouquets can be made, each using k adjacent flowers without reuse.

Nonempty positive bloom days ≤ 10⁹; m ≥ 1 and k ≥ 1. Return −1 if m*k exceeds the number of flowers.

Example

[1, 10, 3, 10, 2], m = 3, k = 1 → day 3.

Use the walkthrough below to inspect the input and each state change.

See Earliest bouquet day, step by step

Inspect the comparison, the invariant, and the next boundary.

Answer-space searchk = 1 · m = 3
left1candidate—right10Search candidate values, not input indices
101013210324
Tested candidate / qualifying inputResolved positionParameters shown above
Left
1
Middle
—
Right
10
Step 01 / 5

Search the answer range

The candidate is a day, rather than an input index. Keep the smallest feasible value.

left = 1; right = 10

Recorded result so far

Not resolved
View exact input

Input: [1,10,3,10,2] · k = 1 · m = 3

Put it into code

A flower is available on day d when bloom[i] ≤ d. Count disjoint adjacent runs; availability can only improve on later days.

Indices are zero-based. C++ uses C++17 or later.

def minimum_days(bloom, m, k):
    # Nonempty positive bloom days; m >= 1, k >= 1.
    if m * k > len(bloom):
        return -1
    left, right = min(bloom), max(bloom)
    while left < right:
        mid = left + (right - left) // 2
        bouquets, run = 0, 0
        for day in bloom:
            if day > mid:
                run = 0
            else:
                run += 1
                if run == k:
                    bouquets += 1
                    run = 0
        if bouquets >= m:
            right = mid
        else:
            left = mid + 1
    return left

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap