2251. Number of Flowers in Full Bloom - Explanation

1. Brute Force

Intuition

The most straightforward approach is to check each person's arrival time against every flower's bloom period. A flower is visible to a person if the arrival time falls within the flower's start and end times (inclusive). We count all such flowers for each person.

Algorithm

For each person in the people array, initialize a counter to zero.
For each flower, check if the person's arrival time is within the flower's bloom period (start <= time <= end).
If yes, increment the counter.
Store the count in the result array and return it.

class Solution:
    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:
        res = []

        for time in people:
            cnt = 0
            for start, end in flowers:
                if start <= time <= end:
                    cnt += 1
            res.append(cnt)

        return res

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(m)$ for the output array.

Where $n$ is the size of the array $flowers$ , and $m$ is the size of the array $people$ .

2. Two Min-Heaps

Intuition

Instead of checking every flower for every person, we can process people in sorted order of their arrival times. By using two min-heaps (one for start times, one for end times), we can efficiently track how many flowers have started blooming and how many have finished. The difference gives us the count of flowers currently in bloom.

Algorithm

Sort people by arrival time while preserving their original indices.
Create two min-heaps: one containing all flower start times, another containing all flower end times.
For each person (in sorted order):
- Pop all start times less than or equal to the person's arrival time and increment the count.
- Pop all end times strictly less than the person's arrival time and decrement the count.
- Record the current count for this person's original index.
Return the result array.

class Solution:
    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:
        people = sorted((p, i) for i, p in enumerate(people))
        res = [0] * len(people)
        count = 0

        start = [f[0] for f in flowers]
        end = [f[1] for f in flowers]

        heapq.heapify(start)
        heapq.heapify(end)

        for p, i in people:
            while start and start[0] <= p:
                heapq.heappop(start)
                count += 1
            while end and end[0] < p:
                heapq.heappop(end)
                count -= 1
            res[i] = count

        return res

Time & Space Complexity

Time complexity: $O(m \log m + n \log n)$
Space complexity: $O(m + n)$

Where $n$ is the size of the array $flowers$ , and $m$ is the size of the array $people$ .

3. Min-Heap

Intuition

We can optimize the two-heap approach by sorting the flowers by start time and using only one heap for end times. As we process each person, we push end times of flowers that have started blooming onto the heap. Then we remove flowers that have finished blooming. The heap size represents the current bloom count.

Algorithm

Sort people by arrival time while preserving their original indices.
Sort flowers by their start times.
Use a single min-heap to track end times of currently blooming flowers.
For each person (in sorted order):
- Push the end times of all flowers with start time less than or equal to the person's arrival time.
- Pop all end times strictly less than the person's arrival time (flowers that stopped blooming).
- The heap size is the count of flowers currently in bloom for this person.
Return the result array.

class Solution:
    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:
        people = sorted((p, i) for i, p in enumerate(people))
        res = [0] * len(people)
        flowers.sort()
        end = []

        j = 0
        for p, i in people:
            while j < len(flowers) and flowers[j][0] <= p:
                heapq.heappush(end, flowers[j][1])
                j += 1
            while end and end[0] < p:
                heapq.heappop(end)
            res[i] = len(end)

        return res

Time & Space Complexity

Time complexity: $O(m \log m + n \log n)$
Space complexity: $O(m + n)$

Where $n$ is the size of the array $flowers$ , and $m$ is the size of the array $people$ .

4. Sorting + Two Pointers

Intuition

Rather than using heaps, we can separate the start and end times into two sorted arrays. By sorting people by arrival time and using two pointers to traverse the start and end arrays, we can efficiently count how many flowers have started minus how many have ended at each person's arrival time.

Algorithm

Extract all start times into one array and all end times into another array. Sort both.
Sort people by arrival time while preserving their original indices.
Initialize two pointers i and j for start and end arrays, and a running count.
For each person (in sorted order):
- Advance pointer i through all start times less than or equal to the person's time, incrementing count.
- Advance pointer j through all end times strictly less than the person's time, decrementing count.
- Record the count for this person's original index.
Return the result array.

class Solution:
    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:
        start = sorted(f[0] for f in flowers)
        end = sorted(f[1] for f in flowers)

        res = [0] * len(people)
        peopleIndex = sorted((p, i) for i, p in enumerate(people))

        i = j = count = 0
        for p, index in peopleIndex:
            while i < len(start) and start[i] <= p:
                count += 1
                i += 1
            while j < len(end) and end[j] < p:
                count -= 1
                j += 1
            res[index] = count

        return res

Time & Space Complexity

Time complexity: $O(m \log m + n \log n)$
Space complexity: $O(m + n)$

Where $n$ is the size of the array $flowers$ , and $m$ is the size of the array $people$ .

5. Line Sweep

Intuition

The line sweep technique treats flower blooms as events on a timeline. Each flower creates two events: a +1 at its start time and a -1 at one past its end time. By processing these events in order alongside sorted queries, we maintain a running count of blooming flowers at any point in time.

Algorithm

Create events for each flower: (start, +1) for blooming and (end + 1, -1) for wilting.
Sort all events by time.
Sort people by arrival time while preserving their original indices.
Use a pointer to traverse events. For each person:
- Process all events with time less than or equal to the person's arrival time, updating the running count.
- Record the count for this person's original index.
Return the result array.

class Solution:
    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:
        events = []
        for start, end in flowers:
            events.append((start, 1))
            events.append((end + 1, -1))

        events.sort()
        queries = sorted((p, i) for i, p in enumerate(people))
        res = [0] * len(people)

        count = j = 0
        for time, index in queries:
            while j < len(events) and events[j][0] <= time:
                count += events[j][1]
                j += 1
            res[index] = count

        return res

Time & Space Complexity

Time complexity: $O(m \log m + n \log n)$
Space complexity: $O(m + n)$

Where $n$ is the size of the array $flowers$ , and $m$ is the size of the array $people$ .

Common Pitfalls

Losing Original Person Indices After Sorting

When sorting people by arrival time for efficient processing, you must preserve their original indices to place results in the correct positions. Failing to track original indices means the output array will have counts in the wrong order, causing incorrect results.

Off-by-One Error in Bloom Period Boundaries

A flower blooming from time start to time end is visible at both endpoints (inclusive). When using events or comparisons, ensure you use <= for start times and < for end times (when checking if a flower has stopped blooming before a person arrives). Using strict inequality for start or inclusive for end will miscount flowers.

Incorrect Event Timing in Line Sweep

In the line sweep approach, the end event should be placed at end + 1, not at end. This is because a flower is still in bloom at time end. Placing the decrement event at end would incorrectly reduce the count for people arriving exactly at the end time.

Not Sorting Events Correctly When Times Are Equal

When multiple events occur at the same time, the order of processing matters. Start events should generally be processed before queries at the same time, and queries before end events. Incorrect tie-breaking in sorting can lead to flowers being counted or not counted incorrectly for edge cases.