Number of Flowers in Full Bloom
HardPrompt
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 * 104flowers[i].length == 21 <= starti <= endi <= 1091 <= people.length <= 5 * 1041 <= people[i] <= 109
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
-
- Initialize an integer array
ansof sizepeople.length.
- Initialize an integer array
-
- For each person
ifrom0topeople.length - 1:
- For each person
-
- Initialize
count = 0.
- Initialize
-
- Let
arrivalTime = people[i].
- Let
-
- For each
flowerinflowers:
- For each
-
-
If `flower[0] <= arrivalTime <= flower[1]`, increment `count`.
-
-
- Set
ans[i] = count.
- Set
-
- Return
ans.
- Return
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.
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; }}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.
Solutions
Solution
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; }}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.