Skip to main content
Talentd

Number of Flowers in Full Bloom - Solution & Explanation

HardArrayHash TableBinary SearchSorting15 min readAsked at: Capital One, Uber, Roblox +4
Practice this problem

Problem Statement

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:

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

Approach Overview

Problem Overview: You are given flower bloom intervals where flowers[i] = [start, end]. Each person arrives at a specific time, and you must return how many flowers are blooming at that exact moment. A flower counts as blooming if start ≤ time ≤ end. The challenge is answering many queries efficiently without scanning every interval each time.

Approach 1: Binary Search on Start and End Times (O((n + q) log n) time, O(n) space)

Separate the start times and end times into two arrays and sort them. For a person arriving at time t, use binary search to count how many flowers have started blooming (start ≤ t) and how many have already finished (end < t). The number of active flowers equals started - ended. Each query runs in O(log n), making this efficient even with thousands of people. This approach works well because the bloom condition depends only on relative ordering of times, not the original interval structure.

Approach 2: Two-Pointer Sweep Line (O((n + q) log(n + q)) time, O(n) space)

This method treats the problem as a sweep line over time. Sort the flowers by start time and also sort the people by arrival time while keeping their original indices. Use two pointers to track which flowers start blooming and which ones finish as time moves forward. Increment a counter when a flower starts and decrement when it ends before the current time. As you process each person in sorted order, the counter represents the number of flowers currently blooming. This technique resembles event processing and often appears in array interval problems and sweep-line algorithms.

Recommended for interviews: The binary search method is the most commonly expected solution. It demonstrates strong understanding of sorting and query optimization with binary search. The sweep line or two-pointer approach shows deeper knowledge of event ordering and interval processing. Mentioning both signals that you recognize multiple ways to convert interval queries into efficient lookups instead of brute force scanning.

Approach 1: Binary Search Approach

This approach involves sorting the start and end times of the flowers separately. For each person’s arrival time, we use binary search to determine how many flowers have started blooming and how many have stopped. The difference will give us the number of flowers in full bloom.

In this implementation, we first extract and sort the start and end times separately. When iterating over each person's arrival time, we use bisect_right to count how many flowers have started to bloom by that time and bisect_left to count how many flowers have finished blooming by that time. The difference gives the number of flowers that are blooming.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O((m + n) log m), where m is the number of flowers and n is the number of people.
Space Complexity: O(m), since we store the start and end times separately.

Try this approach in the editor →

Approach 2: Two-pointer Technique

This approach optimizes the flower counting by utilizing a two-pointer method after sorting both the start and end times, as well as people’s arrival times. This helps reduce unnecessary recomputation and simplifies the logic.

This JavaScript solution employs the two-pointer technique to traverse sorted start and end times while adjusting the count of currently blooming flowers. The people’s arrival times are first mapped to their original indices and sorted, ensuring the results are recorded in the correct order.

Code

JavaScript

JavaScript

Complexity

Time Complexity: O(m log m + n log n), where m is the number of flowers and n is the number of people, containing costs for sorting and linear traversal.
Space Complexity: O(m + n), for holding sorted intervals and the result array.

Try this approach in the editor →

Approach 3: 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.

The time complexity is O((m + n) times log n), and the space complexity is O(n). Here, n and m are the lengths of the arrays flowers and people, respectively.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Approach 4: 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.

The time complexity is O(m times log m + n times log n), and the space complexity is O(n + m). Here, n and m are the lengths of the arrays flowers and people, respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Binary Search Approach

Time Complexity: O((m + n) log m), where m is the number of flowers and n is the number of people.
Space Complexity: O(m), since we store the start and end times separately.

Two-pointer Technique

Time Complexity: O(m log m + n log n), where m is the number of flowers and n is the number of people, containing costs for sorting and linear traversal.
Space Complexity: O(m + n), for holding sorted intervals and the result array.

Sorting + Binary Search—
Difference Array + Sorting + Offline Query—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Binary Search on Start/End ArraysO((n + q) log n)O(n)Best general solution for many queries; simple and interview-friendly
Two-Pointer Sweep LineO((n + q) log(n + q))O(n)Useful when processing events chronologically or implementing interval sweeps

Video Solution

Number of Flowers in Full Bloom - Leetcode 2251 - Python • NeetCodeIO • 15,991 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Number of Flowers in Full Bloom easy or hard?
LeetCode classifies Number of Flowers in Full Bloom as a Hard problem. The difficulty comes from recognizing that direct interval scanning is too slow and transforming the problem into sorted start/end arrays with binary search or a sweep-line algorithm.
Number of Flowers in Full Bloom Python/Java solution
Python and C++ implementations typically use the binary search method with the bisect library or STL functions. JavaScript solutions often implement a sweep-line or two-pointer technique after sorting flowers and queries. All versions aim for O((n + q) log n) performance.
How to solve Number of Flowers in Full Bloom in O(n)?
A near-linear approach uses a sweep line with two pointers after sorting events. Sort flowers by start time and process people in chronological order. Move pointers to add flowers when they start and remove them when they end, maintaining a running bloom count. The main cost comes from sorting, resulting in O((n + q) log(n + q)).
What is the best approach for Number of Flowers in Full Bloom?
The most efficient and commonly used approach is sorting start and end times separately and answering each query using binary search. For a person arriving at time t, count flowers that started blooming (start ≤ t) and subtract flowers that already ended (end < t). This gives O((n + q) log n) time complexity with O(n) space.
Is Number of Flowers in Full Bloom asked at Google/Amazon/Meta?
Interval query and sweep-line problems similar to this appear frequently in interviews at companies like Google, Amazon, and Meta. The problem tests binary search on sorted data, event processing, and efficient handling of multiple queries over intervals.
What data structure is used in Number of Flowers in Full Bloom?
Typical solutions use sorted arrays combined with binary search. Some variations use sweep line techniques with two pointers or event sorting. These approaches rely on fundamental structures such as arrays, sorting, and binary search rather than complex trees.
What is the time complexity of Number of Flowers in Full Bloom?
The optimal solution runs in O((n + q) log n) time, where n is the number of flowers and q is the number of people. Sorting the start and end arrays takes O(n log n), and each query uses binary search in O(log n). Space complexity is O(n) for storing sorted arrays.

Ready to solve this problem?

Practice Number of Flowers in Full Bloom with our built-in code editor and test cases.

Practice on FleetCode
Previous

Meeting Rooms II

Next

Minimum Interval to Include Each Query