# Number of Flowers in Full Bloom
**Difficulty:** HARD
[External](https://leetcode.com/problems/number-of-flowers-in-full-bloom)
Canonical: https://scaleengineer.com/dsa/problems/number-of-flowers-in-full-bloom
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table, Ordered Set
**Companies:** [Roblox](https://scaleengineer.com/companies/roblox), [Capital One](https://scaleengineer.com/companies/capital-one), [Netflix](https://scaleengineer.com/companies/netflix), [PhonePe](https://scaleengineer.com/companies/phonepe), [Databricks](https://scaleengineer.com/companies/databricks), [Samsara](https://scaleengineer.com/companies/samsara)
---
## Problem
You are given a **0-indexed** 2D integer array `flowers`, where `flowers[i] = [starti, endi]` means the `ith` flower will be in **full bloom** from `starti` to `endi` (**inclusive**). You are also given a **0-indexed** integer array `people` of size `n`, where `people[i]` is the time that the `ith` 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_ `ith` _person arrives._

**Example 1:**

![](https://assets.glich.co/dsa/number-of-flowers-in-full-bloom/image0.jpg) 

**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:**

![](https://assets.glich.co/dsa/number-of-flowers-in-full-bloom/image1.jpg) 

**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 * 104`
* `flowers[i].length == 2`
* `1 <= starti <= endi <= 109`
* `1 <= people.length <= 5 * 104`
* `1 <= people[i] <= 109`

# Approaches
## Brute Force Iteration
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.
**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).
**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.
### Explanation
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.
```java
class Solution {
    public int[] fullBloomFlowers(int[][] flowers, int[] people) {
        int n = people.length;
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            int time = people[i];
            int count = 0;
            for (int[] flower : flowers) {
                if (flower[0] <= time && time <= flower[1]) {
                    count++;
                }
            }
            ans[i] = count;
        }
        return ans;
    }
}
```
### Algorithm
- 1. Initialize an integer array `ans` of size `people.length`.
- 2. For each person `i` from `0` to `people.length - 1`:
- 3.    Initialize `count = 0`.
- 4.    Let `arrivalTime = people[i]`.
- 5.    For each `flower` in `flowers`:
- 6.        If `flower[0] <= arrivalTime <= flower[1]`, increment `count`.
- 7.    Set `ans[i] = count`.
- 8. Return `ans`.

## Separate Sorting and Binary Search
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.
**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.
**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.
### Explanation
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:
1. **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.
2. **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.
```java
import java.util.Arrays;

class Solution {
    public int[] fullBloomFlowers(int[][] flowers, int[] people) {
        int m = flowers.length;
        int[] starts = new int[m];
        int[] ends = new int[m];
        for (int i = 0; i < m; i++) {
            starts[i] = flowers[i][0];
            ends[i] = flowers[i][1];
        }

        Arrays.sort(starts);
        Arrays.sort(ends);

        int n = people.length;
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            int time = people[i];
            int started = binarySearchUpperBound(starts, time);
            int ended = binarySearchLowerBound(ends, time);
            ans[i] = started - ended;
        }
        return ans;
    }

    // Finds number of elements <= target
    private int binarySearchUpperBound(int[] arr, int target) {
        int left = 0, right = arr.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] > target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    // Finds number of elements < target
    private int binarySearchLowerBound(int[] arr, int target) {
        int left = 0, right = arr.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}
```
### Algorithm
- 1. Create two arrays, `starts` and `ends`, of size `flowers.length`.
- 2. Populate `starts` with `flower[0]` and `ends` with `flower[1]` for all flowers.
- 3. Sort the `starts` and `ends` arrays.
- 4. Initialize an answer array `ans` of size `people.length`.
- 5. For each person's arrival time `t` in `people`:
- 6.    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`.
- 7.    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`.
- 8.    The number of blooming flowers is `startedCount - endedCount`. Store this in `ans`.
- 9. Return `ans`.

## Sweep-line Algorithm with Two Pointers
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.
**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.
**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.
### Explanation
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.
```java
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public int[] fullBloomFlowers(int[][] flowers, int[] people) {
        int m = flowers.length;
        int[] starts = new int[m];
        int[] ends = new int[m];
        for (int i = 0; i < m; i++) {
            starts[i] = flowers[i][0];
            ends[i] = flowers[i][1];
        }

        Arrays.sort(starts);
        Arrays.sort(ends);

        int n = people.length;
        int[][] sortedPeople = new int[n][2];
        for (int i = 0; i < n; i++) {
            sortedPeople[i][0] = people[i];
            sortedPeople[i][1] = i;
        }
        Arrays.sort(sortedPeople, Comparator.comparingInt(a -> a[0]));

        int[] ans = new int[n];
        int s_ptr = 0;
        int e_ptr = 0;
        int current_blooming = 0;

        for (int i = 0; i < n; i++) {
            int time = sortedPeople[i][0];
            int originalIndex = sortedPeople[i][1];

            // Count flowers that have started by this time
            while (s_ptr < m && starts[s_ptr] <= time) {
                current_blooming++;
                s_ptr++;
            }

            // Count flowers that have ended before this time
            while (e_ptr < m && ends[e_ptr] < time) {
                current_blooming--;
                e_ptr++;
            }
            
            ans[originalIndex] = current_blooming;
        }

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

# Solutions
### Java

```java
class Solution {
public
  int[] fullBloomFlowers(int[][] flowers, int[] people) {
    int n = flowers.length;
    int[] start = new int[n];
    int[] end = new int[n];
    for (int i = 0; i < n; ++i) {
      start[i] = flowers[i][0];
      end[i] = flowers[i][1];
    }
    Arrays.sort(start);
    Arrays.sort(end);
    int m = people.length;
    int[] ans = new int[m];
    for (int i = 0; i < m; ++i) {
      ans[i] = search(start, people[i] + 1) - search(end, people[i]);
    }
    return ans;
  }
private
  int search(int[] nums, int x) {
    int l = 0, r = nums.length;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (nums[mid] >= x) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> fullBloomFlowers(vector<vector<int>> &flowers,
                               vector<int> &people) {
    int n = flowers.size();
    vector<int> start;
    vector<int> end;
    for (auto &f : flowers) {
      start.push_back(f[0]);
      end.push_back(f[1]);
    }
    sort(start.begin(), start.end());
    sort(end.begin(), end.end());
    vector<int> ans;
    for (auto &p : people) {
      auto r = upper_bound(start.begin(), start.end(), p) - start.begin();
      auto l = lower_bound(end.begin(), end.end(), p) - end.begin();
      ans.push_back(r - l);
    }
    return ans;
  }
};

```

### Python

```python
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]

```