All problems

Minimum Days to Make Bouquets

Medium · binary search

A florist has a row of flowers. Flower i blooms on day bloom_day[i] and stays in bloom from then on.

You want to make m bouquets. A bouquet uses exactly k flowers that are next to each other in the row, and every one of them must already be in bloom. A flower can go into at most one bouquet.

Return the earliest day on which m bouquets can be made. If there are not enough flowers to ever make m bouquets, return -1.

Examples

Example 1

Input: bloom_day = [5, 2, 8, 2, 9, 4], m = 2, k = 2

Output: 8

On day 5 only flowers 0, 1, 3 and 5 are in bloom, which gives one pair (flowers 0 and 1). On day 8 flowers 0 to 3 are all in bloom, which gives two pairs.

Example 2

Input: bloom_day = [4, 4, 4, 9, 4, 4], m = 2, k = 3

Output: 9

The late flower in the middle splits the row until day 9.

Example 3

Input: bloom_day = [3, 6, 1], m = 2, k = 2

Output: -1

Two bouquets of two flowers need four flowers, but there are only three.

Constraints