Number of Flowers in Full Bloom

How it works

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.

Steps

1. Create events for each flower: (start, +1) for blooming and (end + 1, -1) for wilting.
2. Sort all events by time.
3. Sort people by arrival time while preserving their original indices.
4. 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.
5. Return the result array.

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.

Things to watch for

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.

from typing import List

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

class Solution {
public:
    vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& people) {
        vector<pair<int, int>> events;
        for (auto& f : flowers) {
            events.emplace_back(f[0], 1);
            events.emplace_back(f[1] + 1, -1);
        }

        sort(events.begin(), events.end());
        vector<pair<int, int>> queries;
        for (int i = 0; i < people.size(); i++) {
            queries.emplace_back(people[i], i);
        }

        sort(queries.begin(), queries.end());
        vector<int> res(people.size());
        int count = 0, j = 0;

        for (auto& [time, index] : queries) {
            while (j < events.size() && events[j].first <= time) {
                count += events[j++].second;
            }
            res[index] = count;
        }

        return res;
    }
};