⚡Flashcard Drill➔
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

  1. A flower is in bloom at time t when start <= t <= end.
  2. So the count is (number of starts <= t) - (number of ends < t).
  3. Sort the starts and the ends separately, then answer each query with two binary searches.
  4. 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 than t, missing flowers starting exactly at t. Use bisect_right.
  • Using bisect_right(ends, t): that counts ends <= t, which would subtract flowers that are still blooming at t. Use bisect_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.
🎯 Drill This Card Now➔

🧩 Related Heap / Priority Queue Problems