Number of Flowers in Full Bloom — Problem & Solution
Number of Flowers in Full Bloom solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Number of Flowers in Full Bloom is a hard coding problem on arrays, sorting and binary search, asked in Amazon, Google, Meta and Databricks interviews.
- Difficulty: Hard
- Topics: Arrays, Sorting, Binary Search, Prefix Sum
- Asked at: Amazon, Google, Meta, Databricks, PhonePe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A garden has flowers whose blooming windows are given as flowers[i] = [start_i, end_i]: flower i is in full bloom at every time t with start_i <= t <= end_i (both ends inclusive).
Visitors arrive at the times in people; visitor j arrives at people[j].
Return an array answer of the same length as people, where answer[j] is the number of flowers in full bloom when visitor j arrives.
Example 1
Input: flowers = [[1,6],[3,7],[9,12],[4,13]], people = [2,3,7,11]
Output: [1,2,2,2]
Explanation: At time 7 the flowers [3,7] and [4,13] bloom; [1,6] has just ended.
Example 2
Input: flowers = [[1,10],[3,3]], people = [3,3,2]
Output: [2,2,1]
Constraints
1 <= flowers.length <= 5 * 10^4flowers[i].length == 21 <= start_i <= end_i <= 10^91 <= people.length <= 5 * 10^41 <= people[j] <= 10^9
Hints for Number of Flowers in Full Bloom
Hint 1
A flower blooms at time
texactly when it has started bytand has not ended beforet.Hint 2
So the count at
tis (number of starts<= t) minus (number of ends< t) — every flower that ended beforethad also started.Hint 3
Sort the start times and the end times separately; each of the two counts is one binary search.
How to solve Number of Flowers in Full Bloom
Split the intervals into two sorted lists — starts and ends. The number of flowers blooming at t equals the starts at or before t minus the ends strictly before t, and both counts are binary searches.
Approach
- Copy all
start_iinto one array and allend_iinto another; sort both. - For each arrival
t, letstarted= number of starts<= t(upper bound oft). - Let
ended= number of ends< t(lower bound oft). - The answer for that visitor is
started - ended.
Why it works
Every flower with end < t also has start <= end < t, so it is counted in started. Subtracting those leaves exactly the flowers with start <= t <= end. Because the two lists are sorted, the counts are the insertion points found by binary search.
Complexity
- Time —
O((f + p) log f) - Space —
O(f)
Pitfalls
- The bloom window is inclusive at both ends — ends count as
< t, starts as<= t. - Visitors are not sorted; answer them in input order.
- A sweep over sorted events also works, but needs the visitors sorted with their indices kept.
Reference solution
Python
from typing import List
import bisect
def fullBloomFlowers(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)
return [bisect.bisect_right(starts, t) - bisect.bisect_left(ends, t) for t in people]Java
public static int[] fullBloomFlowers(int[][] flowers, int[] people) {
int f = flowers.length;
int[] starts = new int[f], ends = new int[f];
for (int i = 0; i < f; i++) { starts[i] = flowers[i][0]; ends[i] = flowers[i][1]; }
Arrays.sort(starts);
Arrays.sort(ends);
int[] res = new int[people.length];
for (int j = 0; j < people.length; j++) {
res[j] = firstIndexAbove(starts, people[j], true) - firstIndexAbove(ends, people[j], false);
}
return res;
}
static int firstIndexAbove(int[] a, int t, boolean strict) {
int lo = 0, hi = a.length;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (strict ? a[mid] <= t : a[mid] < t) lo = mid + 1; else hi = mid;
}
return lo;
}C++
vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& people) {
vector<int> starts, ends;
for (auto& f : flowers) { starts.push_back(f[0]); ends.push_back(f[1]); }
sort(starts.begin(), starts.end());
sort(ends.begin(), ends.end());
vector<int> res;
for (int t : people) {
int started = upper_bound(starts.begin(), starts.end(), t) - starts.begin();
int ended = lower_bound(ends.begin(), ends.end(), t) - ends.begin();
res.push_back(started - ended);
}
return res;
}JavaScript
var fullBloomFlowers = function(flowers, people) {
var starts = [], ends = [];
for (var i = 0; i < flowers.length; i++) {
starts.push(flowers[i][0]);
ends.push(flowers[i][1]);
}
var asc = function(a, b) { return a - b; };
starts.sort(asc);
ends.sort(asc);
var firstAbove = function(a, t, strict) {
var lo = 0, hi = a.length;
while (lo < hi) {
var mid = (lo + hi) >> 1;
if (strict ? a[mid] <= t : a[mid] < t) lo = mid + 1; else hi = mid;
}
return lo;
};
var res = [];
for (var j = 0; j < people.length; j++) {
var t = people[j];
res.push(firstAbove(starts, t, true) - firstAbove(ends, t, false));
}
return res;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms