Minimum Days to Make Bouquets
Medium About 20 min Free, no account needed
Earliest day enough adjacent flowers have bloomed for all the bouquets.
The brief
Flower i blooms on day bloomDay[i]. A bouquet needs k adjacent bloomed
flowers, and each flower is used at most once. Return the earliest day on
which m bouquets can be made, or -1 if impossible.
The obvious approach simulates day 1, 2, 3, ... until enough bouquets form. The hidden
test blooms on days up to 200,000 and needs nearly all of them, so a linear
day-walk with an O(n) count per day is too slow. Note that "enough bouquets by
day d" is monotonic in d, and you will need to exploit that rather than try
every day.
Starter code
using System;
public class Solution
{
// TODO: return the earliest day allowing m bouquets of k adjacent bloomed flowers; -1 if impossible.
public int MinDays(int[] bloomDay, int m, int k)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Binary search on the answer
- Search the space of candidate answers when feasibility is monotonic.
Related katas
- Cutting Ribbons Medium Free The longest equal piece length that still yields k pieces.
- Koko Eating Bananas Medium Free The slowest eating speed that still finishes every pile in time.
- Ship Packages Within D Days Medium Free Smallest ship capacity that delivers the conveyor belt on schedule.
- Integer Square Root Easy Free Floor of the square root, found without floating point.