NeetCode #553LC-2251HardHeap / Priority Queue
← Back to All Problems#553 · #2251 · Number of Flowers in Full Bloom(花期内花的数目)
📌 Problem Statement & Constraints
You are given
flowers where flowers[i] = [start, end] is the blooming interval of the i-th flower, and people where people[i] is an arrival time. Return the number of flowers in bloom at each arrival. Constraints: 1 <= flowers.length, people.length <= 5 * 10^4, 1 <= start <= end <= 10^9, 1 <= people[i] <= 10^9.💡 Core Algorithmic Approaches
- A flower is in bloom at time
twhenstart <= t <= end. - So the count is
(number of starts <= t) - (number of ends < t). - Sort the starts and the ends separately, then answer each query with two binary searches.
- This is O((n + q) log n), far better than a sweep over the (very large) time axis.
💻 Benchmark Python3 Implementation
class Solution:
def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:
from bisect import bisect_right, bisect_left
starts = sorted(f for f, _ in flowers)
ends = sorted(e for _, e in flowers)
# starts <= t minus ends < t
return [bisect_right(starts, t) - bisect_left(ends, t) for t in people]⚡ Complexity Deep Dive
⏱️ Time Complexity
O((n + q) log n): two sorts and two binary searches per query.
💾 Space Complexity
O(n) for the sorted arrays.
⚠️ Interview Pitfalls & Follow-ups
- Using
bisect_left(starts, t): that counts starts strictly less thant, missing flowers starting exactly att. Usebisect_right. - Using
bisect_right(ends, t): that counts ends<= t, which would subtract flowers that are still blooming att. Usebisect_left. - Sweeping the time axis with an array: the times reach 10^9.
- Sorting the queries: unnecessary; each query is independent.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.