Number of Flowers in Full Bloom

Number of Flowers in Full Bloom

What is this problem about?

The Number of Flowers in Full Bloom problem gives you flowers as [start, end] intervals and a list of query times. For each query time, count how many flowers are in bloom (their interval contains the query time). This hard coding problem uses binary search on sorted start and end times to answer each query efficiently.

Why is this asked in interviews?

Databricks, Uber, Netflix, Amazon, and Google ask this because it requires an efficient query approach — O(n log n) preprocessing + O(log n) per query — using binary search on sorted arrays. The array, hash table, sorting, binary search, ordered set, and prefix sum interview pattern is fully exercised.

Algorithmic pattern used

Sort starts and ends + binary search per query. Sort all flower start times and all flower end times separately. For a query time t: count flowers that have started by time t = bisect_right(starts, t). Count flowers that have ended before time t = bisect_left(ends, t). In-bloom count = started - ended.

Example explanation

Flowers: [[1,6],[3,7],[9,12],[4,13]]. Queries: [2,3,7,11]. Starts sorted: [1,3,4,9]. Ends sorted: [6,7,12,13].

• Query t=2: started=1(bisect_right([1,3,4,9],2)=1), ended=0(bisect_left([6,7,12,13],2)=0). In bloom=1.
• Query t=7: started=3, ended=1(bisect_left([6,7,12,13],7)=1). In bloom=2.
• Query t=11: started=4, ended=2. In bloom=2.

Common mistakes candidates make

• Using bisect_left for starts (should be bisect_right — count all starts ≤ t).
• Using bisect_right for ends (should be bisect_left — count ends strictly < t, i.e., ended before t).
• Not sorting starts and ends independently.
• Linear scan per query (O(n*q) total instead of O((n+q) log n)).

Interview preparation tip

The "count intervals containing a point" query always decomposes into: count starts ≤ t minus count ends < t. Using bisect_right for starts and bisect_left for ends is the correct combination. Practice this technique on "number of events active at time t" variants — it appears in scheduling, calendar, and range query problems. The offline query approach (sort queries and use two pointers) is an alternative worth knowing.