Coding · Binary search
Minimum Days to Make m Bouquets
- Reported once
- Medium
- SDE-2
- 1 source
One candidate write-up. Treat it as a single data point.
Solve it in the playground, with tests
Flowers stand in a row, and bloomDay[i] is the day flower i opens. A bouquet needs exactly k flowers that are next to each other in the row and all open, and each flower can go into at most one bouquet. Return the earliest day on which you can have m bouquets, or -1 if the row is too short. For bloomDay [1,10,2,9,3,8,4,7,5,6], m = 4 and k = 2 the answer is 9. The row holds up to 100,000 flowers and days go up to a billion, so trying day after day is far too slow.
Restated in our own words, not a quote from Swiggy or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
A single July 2025 SDE-2 offer post lists this problem, as Minimum Days to Make Bouquets of k Adjacent Flowers, among five problems, and the index shows only that title, so the exact wording the candidate saw is not on file. I would therefore restate it and solve the standard version: flowers in a row, a bouquet is exactly k adjacent open flowers, each flower is used at most once, and the answer is the earliest day with m bouquets. I would confirm that adjacent means neighbours in the row, that a flower can be used on or after its bloom day, and that -1 is returned when m times k exceeds the number of flowers.
Assumptions I would state: m and k are at least 1, days are positive integers, and the flowers stay open once they bloom.
Brute force
Say the obvious answer and why it is too slow.
Walk the days from the earliest bloom to the latest. For each day, scan the row to count how many bouquets can be made, and stop at the first day that reaches m. Each scan is O(n), and with days up to a billion that is O(n times the range of days), which is unusable.
Only days that equal some bloom day can matter, since nothing changes in between. Sorting the distinct bloom days and trying each one cuts it to O(n²) in the worst case. That is the right observation, but it still scans the whole row for every candidate day.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(n × D) day by day, O(n²) over distinct days
- Time
- O(n log D), D is the range of bloom days
- Space
- O(1)
The pattern is binary search on the answer. Ask a yes or no question about a day d: can m bouquets be made by day d? That answer is monotone. If it is yes on day d, it is yes on d + 1, because flowers only open and never close. A monotone yes or no over a sorted range of days means we can binary search for the first yes.
The check is a greedy scan. Walk the row keeping a run of consecutive open flowers. An open flower extends the run, and when the run reaches k, count one bouquet and reset the run to zero. A closed flower resets the run to zero. Cutting a bouquet as early as possible is optimal because, inside a stretch of r open flowers, the most bouquets possible is r divided by k rounded down, and the early cut reaches exactly that.
The search range is from the earliest bloom day to the latest. Before the earliest day nothing is open. On the latest day everything is open, so after the -1 check (m times k at most n) at least m bouquets exist. Keep low and high with the invariant that the answer lies in [low, high]. Take mid = floor((low + high) / 2). If mid works, set high = mid, since mid may itself be the answer. Otherwise set low = mid + 1. When they meet, that day is the answer.
Out loud: "I binary search the day. For a fixed day, one pass counts the bouquets greedily. About 30 passes cover a billion days."
Walk it through
A dry run on the example, step by step.
| Low | High | Mid | Bouquets | Move |
|---|---|---|---|---|
| 1 | 10 | 5 | 0 | low = mid + 1 |
| 6 | 10 | 8 | 3 | low = mid + 1 |
| 9 | 10 | 9 | 4 | high = mid |
| 9 | 9 | - | - | answer 9 |
Open on the whiteboardDraws the structure and its pointers for every row of this dry run, one step at a time.
Take bloomDay [1,10,2,9,3,8,4,7,5,6] with m = 4 and k = 2. The row has ten flowers and four bouquets of two need eight, so it is possible. The range is day 1 to day 10.
Mid is 5. The open flowers are 1, 2, 3, 4 and 5, but each is separated by a closed one, so no pair of neighbours exists: 0 bouquets, so low becomes 6. Mid is 8. Everything except the 10 and the 9 is open, which leaves the single flower 1, the single flower 2, and a run of six, so only 3 bouquets: low becomes 9. Mid is 9. Only the 10 is closed, so one flower is left alone and a run of eight gives 4 bouquets, so high becomes 9. Low equals high, and the answer is 9.
The code
Runnable JavaScript, checked against test cases.
function minDays(bloomDay, m, k) {
if (m * k > bloomDay.length) return -1;
let low = bloomDay[0];
let high = bloomDay[0];
for (const day of bloomDay) {
if (day < low) low = day;
if (day > high) high = day;
}
while (low < high) {
const mid = Math.floor((low + high) / 2);
if (bouquetsBy(bloomDay, k, mid) >= m) high = mid;
else low = mid + 1;
}
return low;
}
function bouquetsBy(bloomDay, k, day) {
let bouquets = 0;
let run = 0;
for (const bloom of bloomDay) {
if (bloom <= day) {
run++;
if (run === k) {
bouquets++;
run = 0;
}
} else {
run = 0;
}
}
return bouquets;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
Too few flowers: if m times k exceeds the number of flowers, return -1 before searching. An empty row also returns -1.
- k = 1: every open flower is a bouquet, so the answer is the m-th smallest bloom day.
- One bouquet using the whole row: the answer is the latest bloom day.
- All days equal: low equals high at the start and the loop is skipped.
- Huge days: the midpoint is computed from values up to a billion, which fits comfortably in a JavaScript number. In a 32-bit language write low + (high - low) / 2 and compute m times k in 64 bits.
- A bloom day exactly equal to mid: that flower counts as open, so the comparison is less-or-equal.
Follow-ups to expect
Where the interviewer pushes next.
- How would you return the positions of the flowers in each bouquet for the answer day?
- How would you adapt it if a bouquet needed k flowers that need not be adjacent?
- How would you answer many queries with different m and k on the same row?
- How does this compare with the problems on finding the smallest speed or capacity, and what do they share?
- How would you search if bloom days were real numbers instead of integers?
Where candidates slip
The mistakes this problem punishes.
The most frequent slip is ignoring adjacency and returning the day when at least m times k flowers are open, then dividing by k. Open flowers that are separated by closed ones cannot be combined.
- Not resetting the run when a flower is closed.
- Not resetting the run after a bouquet is cut, so a run of 2k flowers yields one bouquet instead of two.
- Searching the index of the flowers instead of the days.
- Mixing the two update styles, for example high = mid - 1 together with the loop test low < high, which can skip the answer.
- Sorting the bloom days, which destroys the adjacency the problem depends on.
- Forgetting the -1 case and returning the latest bloom day.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.