DSA Factory
Free Binary search lessonsBinary search · Stage 4 · Real-world bounds · Step 4

The first day that works

Find the earliest day on which you can make enough bouquets from neighbouring flowers, by searching days and counting runs. About 15 minutes.

Runs of bloomed flowers

A garden has a row of flowers, and flower i blooms on day bloom i. To make a bouquet you need k flowers that are next to each other and all bloomed. You want m bouquets. What is the earliest day you can have them?

For a chosen day, mark which flowers have bloomed. A bouquet needs k neighbours in a row, so walk along and keep a run of bloomed flowers. When the run reaches k, you have one bouquet, so count it and start a fresh run. An unbloomed flower breaks the run.

Run reaches k: one bouquet; start a fresh run.
Unbloomed flower: resets the run to zero.
In code
run = best = 0
for b in bloom:
    if b <= day:
        run += 1
        best = max(best, run)
    else:
        run = 0
Flowers bloom on days 3, 3, 8, 3, 3, 3, 3. Two bouquets of 3 neighbours. Earliest day?
123
low
3
high
8
middle
5
bouquets on that day
1

Days range from 3 to 8. On day 5 every flower except the third has bloomed. The first two are too few, and the last four give one bouquet. Only 1 bouquet, so look later.

Move 1 of 3

Search the days

First, if you need more flowers than the garden has, that is m times k above the number of flowers, the answer is -1 whatever the day. Otherwise some day works: the day the last flower blooms.

The earliest and latest bloom days bound your search. If the middle day gives enough bouquets, the answer is that day or earlier, so keep it. If not, the answer is later.

Not enough flowers: m × k above the garden size means -1.
Enough bouquets: keep mid, look earlier.
In code
if m * k > len(bloom):
    return -1   # not enough flowers
Quick check

On some day you can make enough bouquets. What about any later day?

  1. AYou can still make enough, since flowers don't fade
  2. BIt might not be enough
  3. CYou can make fewer bouquets
Show the answer

You can still make enough, since flowers don't fade. More flowers are bloomed on a later day, so runs only get longer.

Your problem

First day with enough bouquets

bloom[i] is the day on which flower i of a row blooms, and it stays bloomed afterwards. A bouquet needs k flowers that are next to each other in the row and all bloomed, and each flower can be used in only one bouquet. Return the smallest day on which you can make m bouquets, or -1 if it is impossible.

Example
bloom = [7, 7, 7, 7, 12, 7, 7], m = 2, k = 3 → 12

1 ≤ flowers ≤ 100,000 · 1 ≤ bloom[i] ≤ 1,000,000,000 · 1 ≤ m, k ≤ 1,000,000

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.
Sign up free to solve