2251. Number of Flowers in Full Bloom

HardArrayHash TableBinary SearchOrdered SetPrefix SumSorting
Leetcode Link

Problem Description

In this problem, we are dealing with a scenario related to flowers blooming. The input includes two arrays:

  1. A 2D array flowers, where each sub-array contains two elements indicating the start and end of the full bloom period for a particular flower. The flower blooms inclusively from start_i to end_i.
  2. An array persons, where each element represents the time a person arrives to see the flowers.

The goal is to determine how many flowers are in full bloom for each person when they arrive. The output should be an array answer, where answer[i] corresponds to the number of flowers in full bloom at the time the ith person arrives.

Intuition

To solve this problem, we can use a two-step strategy involving sorting and binary search:

  1. Sorting: We separate the start and end times of the bloom periods into two lists and sort them. The sorted start times help us determine how many flowers have started blooming at a given point, and the sorted end times indicate how many flowers have finished blooming.

  2. Binary Search: When a person arrives, we want to count the flowers that have begun blooming but haven't finished. We use the binary search algorithm to find:

    • The index of the first end time that is strictly greater than the arrival time of the person, which indicates how many flowers have finished blooming. We get this number using bisect_left on the sorted end times.
    • The index of the first start time that is greater than or equal to the arrival time, which tells us how many flowers have started to bloom. We use bisect_right for this on the sorted start times.

By subtracting the number of flowers that have finished blooming from those that have started, we get the count of flowers in full bloom when a person arrives. We repeat this process for each person and compile the results into the final answer array.

Learn more about Binary Search, Prefix Sum and Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

How many ways can you arrange the three letters A, B and C?

Solution Approach

The solution approach uses a combination of sorting and binary search to efficiently determine how many flowers are in full bloom for each person's arrival time. Here's the implementation explained step by step:

  1. Sort Starting and Ending Times: First, we extract all the start times and end times from the flowers array into separate lists and sort them:

    1start = sorted(a for a, _ in flowers)
2end = sorted(b for _, b in flowers)

    Sorting these lists allows us to use binary search later on. The start list will be used to determine how many flowers have started blooming by a certain time, and the end list will help determine how many flowers have ended their bloom.

  2. Binary Search for Bloom Count: The next step is to iterate over each person's arrival time p in the persons list and find out the count of flowers in bloom at that particular time. For each p:

    1bisect_right(start, p) - bisect_left(end, p)
    • bisect_right(start, p) finds the index in the sorted start list where p would be inserted to maintain the order. This index represents the count of all flowers that have started blooming up to time p (including p).
    • bisect_left(end, p) finds the index in the sorted end list where p could be inserted to maintain the order. This index signifies the count of flowers that have not finished blooming by time p.

By subtracting the numbers obtained from bisect_left on the end list from bisect_right on the start list, we obtain the total number of flowers in bloom at the arrival time of p.

  1. Compile Results: The above operation is repeated for each person's arrival time, and the results are compiled into the answer list. This list comprehends the count of flowers in bloom for each person, as per their arrival times: 
    1return [bisect_right(start, p) - bisect_left(end, p) for p in persons]

In the end, the answer list is returned, which provides the solution, i.e., the number of flowers in full bloom at the time of each person's arrival.

The algorithms and data structures used here, like sorting and binary search (bisect module in Python), enable us to solve the problem in a time-efficient manner, taking advantage of the ordered datasets for quick lookups.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Example Walkthrough

Imagine we have an array of flowers where the blooms are represented as flowers = [[1,3], [2,5], [4,7]] and an array of persons with arrival times as persons = [1, 3, 5]. We want to find out how many flowers are in full bloom each person sees when they arrive.

First, we need to process the flowers' bloom times. We sort the start times [1, 2, 4] and the end times [3, 5, 7] of the blooming periods.

Now let's walk through the steps to get the number of flowers in bloom for each person:

  1. Person at time 1:

    • Using bisect_right for the sorted start times: bisect_right([1, 2, 4], 1) gives us index 1, indicating one flower has started blooming.
    • Using bisect_left for the end times: bisect_left([3, 5, 7], 1) gives us index 0, indicating no flowers have finished blooming.
    • The difference 1 (started) - 0 (ended) tells us that exactly one flower is in full bloom.

  2. Person at time 3:

    • bisect_right([1, 2, 4], 3) results in index 2, as two flowers have bloomed by time 3.
    • bisect_left([3, 5, 7], 3) gives us index 1, as one flower has stopped blooming.
    • The difference 2 (started) - 1 (ended) is 1, so one flower is blooming for this person.

  3. Person at time 5:

    • bisect_right([1, 2, 4], 5) gives an index of 3 - all three flowers have started blooming by time 5.
    • bisect_left([3, 5, 7], 5) yields index 2, as two flowers have finished blooming strictly before time 5.
    • The difference 3 (started) - 2 (ended) is 1, indicating that one flower is in bloom when this person arrives.

Thus, for the persons arriving at times 1, 3, and 5, the function will return [1, 1, 1] as the number of flowers in full bloom at each of their arrival times.

Solution Implementation

1from bisect import bisect_right, bisect_left
2
3class Solution:
4    def fullBloomFlowers(self, flowers: List[List[int]], persons: List[int]) -> List[int]:
5        # Sort the start times and end times of the flowers' blooming periods
6        start_times = sorted(start for start, _ in flowers)
7        end_times = sorted(end for _, end in flowers)
8      
9        # Calculate the number of flowers in full bloom for each person's visit
10        bloom_counts = [
11            # The total number of flowers that have started blooming by person p's visit time
12            bisect_right(start_times, p) - 
13            # Subtracting the number of flowers that have finished blooming by person p's visit time
14            bisect_left(end_times, p) 
15            for p in persons
16        ]
17      
18        return bloom_counts
19
20# Example usage:
21# sol = Solution()
22# print(sol.fullBloomFlowers([[1, 10], [3, 3]], [4, 5]))
23
1import java.util.Arrays;
2
3public class Solution {
4    public int[] fullBloomFlowers(int[][] flowers, int[] people) {
5        int flowerCount = flowers.length;  // Number of flowers
6        int[] bloomStart = new int[flowerCount];
7        int[] bloomEnd = new int[flowerCount];
8
9        // Extract the start and end bloom times for each flower into separate arrays
10        for (int i = 0; i < flowerCount; ++i) {
11            bloomStart[i] = flowers[i][0];
12            bloomEnd[i] = flowers[i][1];
13        }
14
15        // Sort the start and end bloom times arrays
16        Arrays.sort(bloomStart);
17        Arrays.sort(bloomEnd);
18
19        int peopleCount = people.length;  // Number of people
20        int[] answer = new int[peopleCount];  // Array to store the answers
21
22        // For each person, calculate the number of flowers in full bloom
23        for (int i = 0; i < peopleCount; ++i) {
24            // Number of flowers that have started blooming minus
25            // the number of flowers that have already ended blooming
26            answer[i] = findInsertionPoint(bloomStart, people[i] + 1) - findInsertionPoint(bloomEnd, people[i]);
27        }
28
29        return answer; // Return the array containing the number of flowers in full bloom for each person
30    }
31
32    private int findInsertionPoint(int[] times, int value) {
33        int left = 0;  // Start of the search range
34        int right = times.length;  // End of the search range
35
36        // Binary search to find the insertion point of 'value'
37        while (left < right) {
38            int mid = (left + right) / 2; // Midpoint of the current search range
39            if (times[mid] >= value) {
40                right = mid;  // Adjust the search range to the left half
41            } else {
42                left = mid + 1;  // Adjust the search range to the right half
43            }
44        }
45        return left;  // The insertion point is where we would add 'value' to keep the array sorted
46    }
47}
48
1#include <vector>
2#include <algorithm>
3
4using namespace std;
5
6class Solution {
7public:
8    vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& people) {
9        // Number of flower intervals
10        int n = flowers.size();
11
12        // Separate vectors to hold the start and end times for each flower
13        vector<int> starts;
14        vector<int> ends;
15
16        // Loop over all flowers to populate the start and end vectors
17        for (auto& flower : flowers) {
18            starts.push_back(flower[0]);
19            ends.push_back(flower[1]);
20        }
21
22        // Sort the start and end vectors to prepare for binary search
23        sort(starts.begin(), starts.end());
24        sort(ends.begin(), ends.end());
25
26        // Vector to hold the number of flowers in full bloom for each person
27        vector<int> bloomCount;
28
29        // Loop through each person to determine how many flowers are in full bloom
30        for (auto& person : people) {
31            // Find the position of the first flower that starts after the person's time (exclusive)
32            // This gives us the number of flowers that have started blooming
33            auto flowersStarted = upper_bound(starts.begin(), starts.end(), person) - starts.begin();
34
35            // Find the position of the first flower that ends at or before the person's time (inclusive)
36            // This gives us the number of flowers that have already ceased blooming
37            auto flowersEnded = lower_bound(ends.begin(), ends.end(), person) - ends.begin();
38
39            // Subtract flowersEnded from flowersStarted to get the number of flowers in full bloom
40            bloomCount.push_back(flowersStarted - flowersEnded);
41        }
42
43        // Return the counts of flowers in full bloom for each person
44        return bloomCount;
45    }
46};
47
1function fullBloomFlowers(flowers: number[][], people: number[]): number[] {
2    const flowerCount = flowers.length;
3    // Arrays to store the start and end times of each flower's bloom.
4    const bloomStarts = new Array(flowerCount).fill(0);
5    const bloomEnds = new Array(flowerCount).fill(0);
6
7    // Split the flowers' bloom times into start and end times.
8    for (let i = 0; i < flowerCount; ++i) {
9        bloomStarts[i] = flowers[i][0];
10        bloomEnds[i] = flowers[i][1];
11    }
12
13    // Sort the start and end times.
14    bloomStarts.sort((a, b) => a - b);
15    bloomEnds.sort((a, b) => a - b);
16
17    // Array to store the result for each person.
18    const results: number[] = [];
19    for (const person of people) {
20        // Find the number of flowers blooming at the time person visits.
21        const flowersBloomingStart = search(bloomStarts, person + 1); // Start of blooms after person
22        const flowersBloomingEnd = search(bloomEnds, person); // End of blooms by the time person visits
23        results.push(flowersBloomingStart - flowersBloomingEnd); // Number of flowers currently in bloom
24    }
25    return results;
26}
27
28// Binary search helper function to find the index at which a flower's start or end time is greater than or equal to x.
29function search(nums: number[], x: number): number {
30    let left = 0;
31    let right = nums.length;
32    while (left < right) {
33        const mid = left + ((right - left) >> 1); // Prevents potential overflow
34        if (nums[mid] >= x) {
35            right = mid; // Look in the left half
36        } else {
37            left = mid + 1; // Look in the right half
38        }
39    }
40    return left; // Left is the index where nums[left] is >= x
41}
42
Not Sure What to Study? Take the 2-min Quiz๏ผš

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Time and Space Complexity

Time Complexity

The given code consists of three main parts:

  1. Sorting the start times of the flowers: sorted(a for a, _ in flowers)
  2. Sorting the end times of the flowers: sorted(b for _, b in flowers)
  3. Iterating through each person and using binary search to find the count of bloomed flowers: [bisect_right(start, p) - bisect_left(end, p) for p in persons]

Let's consider n as the number of flowers and m as the number of persons. Here's a breakdown of the time complexity:

  • Sorting the start and end times: Sorting takes O(n log n) time for both the start and end lists. Hence the combined sorting time is 2 * O(n log n).
  • Binary search for each person: For each person, bisect_right and bisect_left are performed once. These operations have a time complexity of O(log n). Since these operations are performed for m persons, the total time for this part is O(m log n).

Adding these up, the overall time complexity of the code is O(n log n + m log n).

Space Complexity

The space complexity comes from the additional lists used to store start and end times:

  • Start and end lists: Two lists are created to store start and end times, each of size n. Hence, the space taken by these lists is 2 * O(n).

Therefore, the overall space complexity of the code is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Recommended Readings

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

Prefix Sum

Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ