Number of Flowers in Full Bloom
Asked at Databricks
Problem
You are given a list of flowers, each with a bloom start day and bloom end day. A flower is in full bloom on any day between its start and end (inclusive). Given a list of people who each visit on a specific day, determine how many flowers are in full bloom on each person's visit day.
Asked At
| Company | Difficulty | |
|---|---|---|
| Databricks | HARD | View all Databricks questions → |
How to Think About It
Brute force: for each person, iterate all flowers and count how many are blooming — O(n * m) time.
Sort the bloom start days and bloom end days separately.
For a given day d, the number of blooming flowers = (flowers with start <= d) - (flowers with end < d).
Use binary search on the sorted start and end arrays to compute each count in O(log n).
Optimal: sort starts, sort ends, for each person binary search both arrays — O((n + m) log n) time.
Optimal Approach
Separate the bloom start days and bloom end days into two sorted arrays. For each person arriving on day d, use binary search to find the number of flowers that have started blooming (start <= d) and subtract the number that have already finished blooming (end < d). The result is the count of flowers in full bloom on day d. This gives O((n + m) log n) time where n is the number of flowers and m is the number of people.
What Trips People Up in Real Interviews
Clarify whether the bloom interval is inclusive on both ends — it usually is.
Ask if people can arrive on the same day — yes, and each person's count is independent.
Use bisect_right for end days (flowers with end < d) and bisect_right for start days (flowers with start <= d).
Edge case: a flower that blooms on exactly one day (start == end) should be counted for that day.
Discuss the tradeoff between the sorting + binary search approach vs. a sweep line with a prefix sum.
Solution Code
import bisect
def fullBloomFlowers(flowers, people):
starts = sorted(f[0] for f in flowers)
ends = sorted(f[1] for f in flowers)
result = []
for p in people:
started = bisect.bisect_right(starts, p)
ended = bisect.bisect_left(ends, p)
result.append(started - ended)
return resultFrequently Asked Questions
What is the Number of Flowers in Full Bloom problem?
You are given a list of flowers, each with a bloom start day and bloom end day. A flower is in full bloom on any day between its start and end (inclusive). Given a list of people who each visit on a specific day, determine how many flowers are in full bloom on each person's visit day.
How do you solve Number of Flowers in Full Bloom?
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 Number of Flowers in Full Bloom?
Number of Flowers in Full Bloom is asked at Databricks. It is a hard difficulty problem.
What are common mistakes on Number of Flowers in Full Bloom?
- Clarify whether the bloom interval is inclusive on both ends — it usually is.
- Ask if people can arrive on the same day — yes, and each person's count is independent.
- Use bisect_right for end days (flowers with end < d) and bisect_right for start days (flowers with start <= d).
- Edge case: a flower that blooms on exactly one day (start == end) should be counted for that day.
- Discuss the tradeoff between the sorting + binary search approach vs. a sweep line with a prefix sum.