Minimum Number of Days to Make m Bouquets
Asked at Flipkart
Problem
Minimum Number of Days to Make m Bouquets gives you the day each flower blooms and asks for the earliest day on which you can make m bouquets of k adjacent bloomed flowers each (or -1). It is a textbook "binary search on the answer" problem.
Asked At
| Company | Difficulty | |
|---|---|---|
| Flipkart | Medium | View all Flipkart questions → |
How to Think About It
If you need m * k flowers and there are fewer, the answer is -1 immediately.
Key insight: feasibility is monotone in the day. If you can make m bouquets by day d, you can also do it by any later day. So binary search on d.
Check a day d greedily: scan left to right, counting consecutive bloomed flowers (bloomDay[i] <= d). Every time the run reaches k, form a bouquet and reset the run. A flower that has not bloomed also resets the run.
Search range: from the smallest bloom day to the largest.
Walkthrough: bloomDay = [1,10,3,10,2], m = 3, k = 1. Day 3: bloomed at indices 0, 2, 4 -> 3 bouquets. Day 2 gives only 2. Answer 3.
Optimal Approach
Step 1: If m * k > n, return -1.
Step 2: lo = min(bloomDay), hi = max(bloomDay).
Step 3: While lo < hi:
mid = (lo + hi) // 2
If canMake(mid): hi = mid, else lo = mid + 1.
Step 4: Return lo.
canMake(d): greedy scan counting runs of bloomed flowers.
Time: O(n log D) where D is the day range. Space: O(1).
What Trips People Up in Real Interviews
Checking every day from 1 to max(bloomDay) — up to 10^9 checks.
Overflow computing m * k in C++/Java (10^6 * 10^5). Use a 64-bit type.
Forgetting to reset the run on an unbloomed flower; bouquets need adjacent flowers.
Using lo <= hi with hi = mid, which can loop forever. Match the loop condition to the update rule.
Solution Code
def minDays(bloomDay, m, k):
if m * k > len(bloomDay):
return -1
def can_make(day):
bouquets = run = 0
for b in bloomDay:
if b <= day:
run += 1
if run == k:
bouquets += 1
run = 0
else:
run = 0
return bouquets >= m
lo, hi = min(bloomDay), max(bloomDay)
while lo < hi:
mid = (lo + hi) // 2
if can_make(mid):
hi = mid
else:
lo = mid + 1
return loFrequently Asked Questions
What is the Minimum Number of Days to Make m Bouquets problem?
Minimum Number of Days to Make m Bouquets gives you the day each flower blooms and asks for the earliest day on which you can make `m` bouquets of `k` adjacent bloomed flowers each (or `-1`). It is a textbook "binary search on the answer" problem.
How do you solve Minimum Number of Days to Make m Bouquets?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Minimum Number of Days to Make m Bouquets?
Minimum Number of Days to Make m Bouquets is asked at Flipkart. It is a medium difficulty problem.
What are common mistakes on Minimum Number of Days to Make m Bouquets?
- Checking every day from 1 to `max(bloomDay)` — up to `10^9` checks.
- Overflow computing `m * k` in C++/Java (`10^6 * 10^5`). Use a 64-bit type.
- Forgetting to reset the run on an unbloomed flower; bouquets need adjacent flowers.
- Using `lo <= hi` with `hi = mid`, which can loop forever. Match the loop condition to the update rule.