LeetCode 2251 - Number of Flowers in Full Bloom

LeetCode Problem 2251

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Binary Search, Sorting, Prefix Sum, Ordered Set

Solution

Problem Understanding

The problem asks us to determine, for a list of people arriving at certain times, how many flowers are in full bloom at the time of their arrival. Each flower has a start and end time representing the period it is in full bloom, inclusive of both endpoints. The input consists of a 2D array flowers, where flowers[i] = [starti, endi], and an array people indicating the arrival times of each person. The output is an array answer, where answer[i] is the number of flowers in bloom when people[i] arrives.

Constraints indicate that there can be up to 50,000 flowers and 50,000 people, and the times can go up to 10^9. This tells us that a naive approach checking every flower for each person will be too slow, as it would require up to 2.5 * 10^9 comparisons in the worst case. Edge cases include multiple flowers starting and ending at the same time, people arriving before any flower blooms, and people arriving exactly at a flower's start or end time.

The problem guarantees that start and end times are valid (starti <= endi) and that both arrays are non-empty.

Approaches

The brute-force approach is straightforward: for each person, iterate over all flowers and check if the person's arrival time is within the flower's bloom interval. While this works correctly, it has a time complexity of O(n * m), where n is the number of people and m is the number of flowers. Given the constraints, this approach is too slow.

The optimal approach relies on the observation that if we separate flower start times and end times into two sorted arrays, we can determine the number of flowers in bloom at any time t by counting the number of flowers that have started by t and subtracting the number that have already ended before t. This reduces the problem to sorting and using binary search, which is efficient for large inputs.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * m)	O(1)	Check each flower for each person
Optimal	O(n log n + m log m)	O(n + m)	Sort start and end times, use binary search per person

Algorithm Walkthrough

1. Extract all start times and all end times from flowers into separate arrays starts and ends.

2. Sort both starts and ends arrays in ascending order. This allows us to perform efficient binary searches later.

3. Initialize an empty array answer to store the results for each person.

4. For each person's arrival time p in people:

5. Use binary search (bisect_right) to find the number of flowers whose start time is less than or equal to p. This gives the count of flowers that have started blooming by p.

6. Use binary search (bisect_right) to find the number of flowers whose end time is less than p. This gives the count of flowers that have already ended before p.

7. Subtract the second count from the first count to get the number of flowers in bloom at time p.

8. Append this value to answer.

9. Return the answer array.

Why it works: The invariant here is that at any time p, the number of flowers in bloom equals the number of flowers that have started by p minus those that have already ended before p. Sorting allows us to count these efficiently with binary search.

Python Solution

from bisect import bisect_right
from typing import List

class Solution:
    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:
        starts = sorted(f[0] for f in flowers)
        ends = sorted(f[1] for f in flowers)
        answer = []
        
        for p in people:
            started = bisect_right(starts, p)
            ended = bisect_right(ends, p - 1)
            answer.append(started - ended)
        
        return answer

The solution first sorts the start and end times. For each person's arrival, bisect_right is used to find the number of flowers that have started blooming by that time and the number that have ended before that time. The difference is appended to the result array.

Go Solution

import (
    "sort"
)

func fullBloomFlowers(flowers [][]int, people []int) []int {
    n := len(flowers)
    starts := make([]int, n)
    ends := make([]int, n)
    for i, f := range flowers {
        starts[i] = f[0]
        ends[i] = f[1]
    }
    sort.Ints(starts)
    sort.Ints(ends)

    answer := make([]int, len(people))
    for i, p := range people {
        started := sort.SearchInts(starts, p+1)
        ended := sort.SearchInts(ends, p)
        answer[i] = started - ended
    }
    return answer
}

In Go, sort.SearchInts is used instead of bisect_right. SearchInts(arr, x) returns the index where x would be inserted to keep arr sorted, which corresponds to the number of elements ≤ x-1 depending on how we adjust x. We handle the same calculation logic as Python.

Worked Examples

Example 1: flowers = [[1,6],[3,7],[9,12],[4,13]], people = [2,3,7,11]

Person	Flowers Started	Flowers Ended	In Bloom
2	1	0	1
3	2	0	2
7	3	1	2
11	4	2	2

Example 2: flowers = [[1,10],[3,3]], people = [3,3,2]

Person	Flowers Started	Flowers Ended	In Bloom
3	2	0	2
3	2	0	2
2	1	0	1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n + m log m)	Sorting starts and ends takes O(m log m), binary search for each person takes O(n log m)
Space	O(n + m)	Storing sorted start and end arrays

Sorting and binary search allow the algorithm to handle large inputs efficiently.

Test Cases

# provided examples
assert Solution().fullBloomFlowers([[1,6],[3,7],[9,12],[4,13]], [2,3,7,11]) == [1,2,2,2]  # example 1
assert Solution().fullBloomFlowers([[1,10],[3,3]], [3,3,2]) == [2,2,1]  # example 2

# boundary cases
assert Solution().fullBloomFlowers([[1,1]], [1]) == [1]  # flower blooms exactly at arrival
assert Solution().fullBloomFlowers([[1,2]], [3]) == [0]  # person arrives after bloom
assert Solution().fullBloomFlowers([[5,10],[1,3]], [4,5,10]) == [0,1,1]  # mix before and during blooms

# multiple flowers starting and ending at same time
assert Solution().fullBloomFlowers([[1,5],[1,5],[1,5]], [3,5,6]) == [3,3,0]

# large number test
assert Solution().fullBloomFlowers([[1,1000000000]]*50000, [1,500000000,1000000000]) == [50000,50000,50000]

Test	Why
Example 1	Validates normal multiple overlaps
Example 2	Validates single-day bloom and duplicates
Boundary single bloom	Checks edge of inclusivity
Person after bloom	Checks proper subtraction of ended flowers
Multiple identical flowers	Validates counting of duplicates
Large number	Stress test for performance

Edge Cases

First, a person arriving before any flower blooms. The algorithm correctly counts zero started flowers and zero ended flowers, resulting in zero in bloom.

Second, a person arriving exactly at a flower’s start or end time. Since the start is inclusive, the binary search counts this flower as started. End times are handled as < p, so an end at p does not reduce the count, which preserves inclusivity.

Third, multiple flowers starting and ending at the same time. Sorting ensures that binary search counts all flowers consistently, even if their intervals overlap exactly, so duplicates do not cause off-by-one errors.

This algorithm correctly handles all these edge cases due to the careful use of inclusive/exclusive comparisons combined with sorted binary searches.