#2251

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Number of Flowers in Full Bloom

Find the number of flowers in full bloom at the given times for a list of people.

array hash table binary search sorting prefix sum

Problem Statement

You are given a 0-indexed 2D array flowers where each element represents the blooming time range for a flower. Specifically, flowers[i] = [starti, endi] means the ith flower is in full bloom from time starti to endi, inclusive. Additionally, you are given a 0-indexed array people where people[i] represents the arrival time of the ith person who will observe the flowers.

Your task is to return an array answer of size n, where answer[i] represents the number of flowers in full bloom when the ith person arrives. A flower is considered to be in full bloom at time t if its blooming interval includes time t.

Examples

Example 1

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

Output: [1,2,2,2]

The figure above shows the times when the flowers are in full bloom and when the people arrive. For each person, we return the number of flowers in full bloom during their arrival.

Example 2

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

Output: [2,2,1]

The figure above shows the times when the flowers are in full bloom and when the people arrive. For each person, we return the number of flowers in full bloom during their arrival.

Constraints

1 <= flowers.length <= 5 * 104
flowers[i].length == 2
1 <= starti <= endi <= 109
1 <= people.length <= 5 * 104
1 <= people[i] <= 109

Solution Approach

Sorting the Bloom Intervals and People

Start by sorting the flowers based on their start time and the people based on their arrival time. Sorting helps us to efficiently process the events in chronological order and apply binary search or array scanning for fast lookups.

Using Binary Search for Bloom Count

For each person's arrival time, use binary search to find how many flowers have started blooming up to that point. We can store the bloom intervals in a way that allows us to quickly identify how many flowers have already bloomed before the person's arrival time.

Efficient Result Computation with Hash Maps

As we compute the blooming flowers for each person, store the results in a hash map or a similar data structure. This will allow for quick access and avoid redundant recalculations, improving the overall time complexity.

Complexity Analysis

Metric	Value
Time	O((n + m) \cdot \log{n})
Space	O(n)

The time complexity is O((n + m) \cdot \log{n}), where n is the number of flowers and m is the number of people. This comes from sorting the flowers and people arrays, followed by binary search to find how many flowers are in bloom for each person. The space complexity is O(n), as we store the results in an array for each person and may need to store the flower intervals as well.

What Interviewers Usually Probe

Look for familiarity with binary search and sorting techniques.
Assess the candidate's ability to handle large input sizes with an optimized approach.
Evaluate whether the candidate can effectively apply hash maps and binary search together.

Common Pitfalls or Variants

Common pitfalls

Forgetting to sort the flower intervals and people's arrival times, which will lead to inefficient solutions.
Not utilizing binary search or hash maps, which can result in a slower, less optimized solution.
Misunderstanding the problem by assuming all flowers are blooming at every time point, leading to incorrect results.

Follow-up variants

Consider adding extra constraints, such as limiting the number of flowers or the range of bloom times.
Explore how the solution changes if the flowers' blooming times are not continuous, adding complexity to the bloom intervals.
Alter the problem to calculate the number of flowers in bloom over a specific range of times instead of for individual people.

FAQ

How do I solve the Number of Flowers in Full Bloom problem efficiently?

The key to solving this problem efficiently is sorting both the flowers and the people by time. After sorting, binary search can be used to count how many flowers are in bloom at each person's arrival time.

What is the time complexity of the Number of Flowers in Full Bloom problem?

The time complexity is O((n + m) \cdot \log{n}), where n is the number of flowers and m is the number of people, primarily due to sorting and binary search operations.

Can I use a brute-force solution for this problem?

While a brute-force solution is possible, it will be inefficient for larger inputs due to the high number of comparisons required. The optimal solution uses sorting and binary search to reduce the time complexity.

How do I apply binary search to the Number of Flowers in Full Bloom problem?

Binary search can be applied to find the number of flowers that have started blooming before each person's arrival time, allowing you to count the blooming flowers efficiently.

What data structures are helpful for solving this problem?

Helpful data structures include sorted arrays for the bloom times, binary search for efficient lookup, and hash maps for storing the results of each person's query.

terminal

Solution

Solution 1: Sorting + Binary Search

We sort the flowers by their start and end times. Then, for each person, we can use binary search to find the number of flowers in bloom when they arrive. This means finding the number of flowers that have started blooming by the time each person arrives, minus the number of flowers that have wilted by that time, to get the answer.

1

2

3

4

5

6

class Solution:
    def fullBloomFlowers(
        self, flowers: List[List[int]], people: List[int]
    ) -> List[int]:
        start, end = sorted(a for a, _ in flowers), sorted(b for _, b in flowers)
        return [bisect_right(start, p) - bisect_left(end, p) for p in people]

Solution 2: Difference Array + Sorting + Offline Query

We can use a difference array to maintain the number of flowers at each time point. Next, we sort $people$ by their arrival times in ascending order. When each person arrives, we perform a prefix sum operation on the difference array to get the answer.

1

2

3

4

5

6

class Solution:
    def fullBloomFlowers(
        self, flowers: List[List[int]], people: List[int]
    ) -> List[int]:
        start, end = sorted(a for a, _ in flowers), sorted(b for _, b in flowers)
        return [bisect_right(start, p) - bisect_left(end, p) for p in people]

Continue Practicing

#2713 maximum strictly increasing cells in a matrix #2234 maximum total beauty of the gardens #2271 maximum white tiles covered by a carpet