Number of Flowers in Full Bloom

Hard

#2051Time: O(N * M), where N is the number of people and M is the number of flowers. For each of the N people, we iterate through all M flowers.Space: O(N) for the output array. If the output array is not considered, the space complexity is O(1).6 companies

Patterns

Prefix Sum

Algorithms

Binary Search Sorting

Data structures

Array Hash Table Ordered Set

Companies

Roblox Capital One Netflix PhonePe

Prompt

You are given a 0-indexed 2D integer array flowers, where flowers[i] = [start_i, end_i] means the i^th flower will be in full bloom from start_i to end_i (inclusive). You are also given a 0-indexed integer array people of size n, where people[i] is the time that the i^th person will arrive to see the flowers.

Return an integer array answer of size n, where answer[i] is the number of flowers that are in full bloom when the i^th person arrives.

Example 1:

Input: flowers = [[1,6],[3,7],[9,12],[4,13]], people = [2,3,7,11]
Output: [1,2,2,2]
Explanation: 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]
Explanation: 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 * 10⁴
flowers[i].length == 2
1 <= start_i <= end_i <= 10⁹
1 <= people.length <= 5 * 10⁴
1 <= people[i] <= 10⁹

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. For each person's arrival time, we iterate through every flower's blooming interval to check if the flower is in bloom at that specific time.

Algorithm

1. Initialize an integer array ans of size people.length.
1. For each person i from 0 to people.length - 1:
1. Initialize count = 0.
1. Let arrivalTime = people[i].
1. For each flower in flowers:
1. If `flower[0] <= arrivalTime <= flower[1]`, increment `count`.
1. Set ans[i] = count.
1. Return ans.

Walkthrough

We initialize an answer array, ans, with the same length as the people array. We then loop through each person i. For each person, we get their arrival time t = people[i]. Inside this loop, we start another loop to go through every flower interval [start, end] in the flowers array. For each flower, we check if the person's arrival time t is within the inclusive interval [start, end]. The condition is start <= t && t <= end. We maintain a counter for the current person. If the condition is true, we increment the counter. After checking all flowers for the current person, the final count is stored in ans[i]. This process is repeated for all people. The final ans array is returned.

1class Solution {2    public int[] fullBloomFlowers(int[][] flowers, int[] people) {3        int n = people.length;4        int[] ans = new int[n];5        for (int i = 0; i < n; i++) {6            int time = people[i];7            int count = 0;8            for (int[] flower : flowers) {9                if (flower[0] <= time && time <= flower[1]) {10                    count++;11                }12            }13            ans[i] = count;14        }15        return ans;16    }17}

Complexity

Time

O(N * M), where N is the number of people and M is the number of flowers. For each of the N people, we iterate through all M flowers.

Space

O(N) for the output array. If the output array is not considered, the space complexity is O(1).

Trade-offs

Pros

Simple to understand and implement.

Cons

Very inefficient and will likely result in a Time Limit Exceeded (TLE) error for large inputs due to its quadratic time complexity.

This approach improves upon the brute-force method by pre-processing the flower data. Instead of checking intervals for each person, we can rephrase the problem: for a given time t, how many flowers have started blooming (start <= t) minus how many have finished blooming (end < t)? This can be answered efficiently using binary search on sorted lists of start and end times.

Algorithm

1. Create two arrays, starts and ends, of size flowers.length.
1. Populate starts with flower[0] and ends with flower[1] for all flowers.
1. Sort the starts and ends arrays.
1. Initialize an answer array ans of size people.length.
1. For each person's arrival time t in people:
1. Find startedCount, the number of flowers with start_time <= t, using binary search on starts. This is the index of the first element greater than t.
1. Find endedCount, the number of flowers with end_time < t, using binary search on ends. This is the index of the first element greater than or equal to t.
1. The number of blooming flowers is startedCount - endedCount. Store this in ans.
1. Return ans.

Walkthrough

First, we create two separate arrays, starts and ends, to store the start and end times of all flowers, respectively. We populate these arrays by iterating through the flowers array. Then, we sort both the starts and ends arrays in ascending order. This is the key pre-processing step. For each person's arrival time t in the people array, we perform two binary searches:

Count of flowers started: We use binary search on the starts array to find the number of flowers that have started blooming by time t. This is equivalent to finding the count of start_i <= t. A standard binary search can find the insertion point for t+1 (or find the upper bound for t), which gives us this count.
Count of flowers ended: We use binary search on the ends array to find the number of flowers that have finished blooming before time t. This is equivalent to finding the count of end_i < t. A standard binary search can find the insertion point for t (or find the lower bound for t), which gives us this count. The number of flowers in full bloom at time t is the difference: (flowers started) - (flowers ended). We store this result for each person and return the final answer array.

1import java.util.Arrays;2 3class Solution {4    public int[] fullBloomFlowers(int[][] flowers, int[] people) {5        int m = flowers.length;6        int[] starts = new int[m];7        int[] ends = new int[m];8        for (int i = 0; i < m; i++) {9            starts[i] = flowers[i][0];10            ends[i] = flowers[i][1];11        }12 13        Arrays.sort(starts);14        Arrays.sort(ends);15 16        int n = people.length;17        int[] ans = new int[n];18        for (int i = 0; i < n; i++) {19            int time = people[i];20            int started = binarySearchUpperBound(starts, time);21            int ended = binarySearchLowerBound(ends, time);22            ans[i] = started - ended;23        }24        return ans;25    }26 27    // Finds number of elements <= target28    private int binarySearchUpperBound(int[] arr, int target) {29        int left = 0, right = arr.length;30        while (left < right) {31            int mid = left + (right - left) / 2;32            if (arr[mid] > target) {33                right = mid;34            } else {35                left = mid + 1;36            }37        }38        return left;39    }40 41    // Finds number of elements < target42    private int binarySearchLowerBound(int[] arr, int target) {43        int left = 0, right = arr.length;44        while (left < right) {45            int mid = left + (right - left) / 2;46            if (arr[mid] >= target) {47                right = mid;48            } else {49                left = mid + 1;50            }51        }52        return left;53    }54}

Complexity

Time

O(M log M + N log M), where N is the number of people and M is the number of flowers. Sorting takes O(M log M). Then for each of the N people, we perform two binary searches on arrays of size M, which takes O(log M) each.

Space

O(M + N). We need O(M) space for the `starts` and `ends` arrays and O(N) for the result array.

Trade-offs

Pros

Significantly more efficient than the brute-force approach for large inputs.

Cons

Can be further optimized by avoiding repeated binary searches if the people's arrival times are also sorted.

This is the most efficient approach, often referred to as a sweep-line algorithm. It processes events (flower start, flower end, person arrival) in chronological order. By sorting both the flower times and people's arrival times, we can iterate through them in a coordinated fashion using pointers, calculating the number of blooming flowers incrementally.

Algorithm

1. Create and sort starts and ends arrays from flowers.
1. Create a new data structure (e.g., 2D array) to store [people[i], i] pairs.
1. Sort these pairs based on the arrival time people[i].
1. Initialize s_ptr = 0, e_ptr = 0, and current_blooming = 0.
1. Initialize an answer array ans of size people.length.
1. Iterate through the sorted people pairs [time, original_index]:
1. While s_ptr is within bounds and starts[s_ptr] <= time, increment current_blooming and s_ptr.
1. While e_ptr is within bounds and ends[e_ptr] < time, decrement current_blooming and e_ptr.
1. Set ans[original_index] = current_blooming.
1. Return ans.

Walkthrough

The core idea is to count the net change in blooming flowers as time progresses. A flower starting to bloom is a +1 event, and a flower ending its bloom is a -1 event. First, create and sort starts and ends arrays from the flowers data, just like in the previous approach. To handle the people's arrival times in order while preserving their original positions for the output, we create a 2D array or a list of pairs, sortedPeople, where each element is [arrivalTime, originalIndex]. We then sort this sortedPeople array based on arrivalTime. We initialize pointers for the starts array (s_ptr), the ends array (e_ptr), and a variable current_blooming to 0. We iterate through the sortedPeople array. For each person [time, orig_idx]:

We advance s_ptr through the starts array, incrementing current_blooming for every flower that starts blooming on or before the current person's arrival time (starts[s_ptr] <= time).
We advance e_ptr through the ends array, decrementing current_blooming for every flower that has finished blooming before the person's arrival (ends[e_ptr] < time).
After these updates, current_blooming holds the exact number of flowers in bloom at time. We store this value in our answer array at the person's original index: ans[orig_idx] = current_blooming. After iterating through all people, the ans array is complete and can be returned.

1import java.util.Arrays;2import java.util.Comparator;3 4class Solution {5    public int[] fullBloomFlowers(int[][] flowers, int[] people) {6        int m = flowers.length;7        int[] starts = new int[m];8        int[] ends = new int[m];9        for (int i = 0; i < m; i++) {10            starts[i] = flowers[i][0];11            ends[i] = flowers[i][1];12        }13 14        Arrays.sort(starts);15        Arrays.sort(ends);16 17        int n = people.length;18        int[][] sortedPeople = new int[n][2];19        for (int i = 0; i < n; i++) {20            sortedPeople[i][0] = people[i];21            sortedPeople[i][1] = i;22        }23        Arrays.sort(sortedPeople, Comparator.comparingInt(a -> a[0]));24 25        int[] ans = new int[n];26        int s_ptr = 0;27        int e_ptr = 0;28        int current_blooming = 0;29 30        for (int i = 0; i < n; i++) {31            int time = sortedPeople[i][0];32            int originalIndex = sortedPeople[i][1];33 34            // Count flowers that have started by this time35            while (s_ptr < m && starts[s_ptr] <= time) {36                current_blooming++;37                s_ptr++;38            }39 40            // Count flowers that have ended before this time41            while (e_ptr < m && ends[e_ptr] < time) {42                current_blooming--;43                e_ptr++;44            }45            46            ans[originalIndex] = current_blooming;47        }48 49        return ans;50    }51}

Complexity

Time

O(M log M + N log N). Sorting `starts` and `ends` takes O(M log M). Sorting `people` with their indices takes O(N log N). The final coordinated traversal takes O(M + N) because each pointer only moves forward. The dominant part is the sorting.

Space

O(M + N). We need O(M) for `starts` and `ends`, and O(N) for storing sorted people with indices and for the result array.

Trade-offs

Pros

Most efficient solution with optimal time complexity. It avoids redundant computations by processing events in a single pass after sorting.

Cons

Slightly more complex to implement due to the need to track original indices and manage multiple pointers.

Solutions

Solution

1class Solution {2public3  int[] fullBloomFlowers(int[][] flowers, int[] people) {4    int n = flowers.length;5    int[] start = new int[n];6    int[] end = new int[n];7    for (int i = 0; i < n; ++i) {8      start[i] = flowers[i][0];9      end[i] = flowers[i][1];10    }11    Arrays.sort(start);12    Arrays.sort(end);13    int m = people.length;14    int[] ans = new int[m];15    for (int i = 0; i < m; ++i) {16      ans[i] = search(start, people[i] + 1) - search(end, people[i]);17    }18    return ans;19  }20private21  int search(int[] nums, int x) {22    int l = 0, r = nums.length;23    while (l < r) {24      int mid = (l + r) >> 1;25      if (nums[mid] >= x) {26        r = mid;27      } else {28        l = mid + 1;29      }30    }31    return l;32  }33}

1class Solution {2public:3  vector<int> fullBloomFlowers(vector<vector<int>> &flowers,4                               vector<int> &people) {5    int n = flowers.size();6    vector<int> start;7    vector<int> end;8    for (auto &f : flowers) {9      start.push_back(f[0]);10      end.push_back(f[1]);11    }12    sort(start.begin(), start.end());13    sort(end.begin(), end.end());14    vector<int> ans;15    for (auto &p : people) {16      auto r = upper_bound(start.begin(), start.end(), p) - start.begin();17      auto l = lower_bound(end.begin(), end.end(), p) - end.begin();18      ans.push_back(r - l);19    }20    return ans;21  }22};

1class Solution:2    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]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2public3  int[] fullBloomFlowers(int[][] flowers, int[] people) {4    int n = flowers.length;5    int[] start = new int[n];6    int[] end = new int[n];7    for (int i = 0; i < n; ++i) {8      start[i] = flowers[i][0];9      end[i] = flowers[i][1];10    }11    Arrays.sort(start);12    Arrays.sort(end);13    int m = people.length;14    int[] ans = new int[m];15    for (int i = 0; i < m; ++i) {16      ans[i] = search(start, people[i] + 1) - search(end, people[i]);17    }18    return ans;19  }20private21  int search(int[] nums, int x) {22    int l = 0, r = nums.length;23    while (l < r) {24      int mid = (l + r) >> 1;25      if (nums[mid] >= x) {26        r = mid;27      } else {28        l = mid + 1;29      }30    }31    return l;32  }33}

1class Solution {2public:3  vector<int> fullBloomFlowers(vector<vector<int>> &flowers,4                               vector<int> &people) {5    int n = flowers.size();6    vector<int> start;7    vector<int> end;8    for (auto &f : flowers) {9      start.push_back(f[0]);10      end.push_back(f[1]);11    }12    sort(start.begin(), start.end());13    sort(end.begin(), end.end());14    vector<int> ans;15    for (auto &p : people) {16      auto r = upper_bound(start.begin(), start.end(), p) - start.begin();17      auto l = lower_bound(end.begin(), end.end(), p) - end.begin();18      ans.push_back(r - l);19    }20    return ans;21  }22};

1class Solution:2    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]

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.