< Back





2251. Number of Flowers in Full Bloom

We're given a list of flowers with format [(start_i, end_i) ... (start_n, end_n)], and a list of
people where people[i] is the time when a person will be present. We're asked to return a list
correlating with people that determines the number of flowers that will be in full bloom when
person[i] is present.

The most intuitive way to solve this is to pre-process the input flowers list, creating a list of
start and end times, sorted in ascending order. For each person, we'll maintain two pointers for
the start and end times, i and j. i will describe the number of flowers that bloom before or during
a person's visit. j will describe the number of flowers that stop blooming before the person's visit.
We find i and j by binary searching through the start and end times with the time person[i] appears.

Taking the difference of i and j, we can determine the number of flowers in full bloom when person[i]
is present. We repeat this process for each person and return the list of flowers in full bloom.

The solution is as follows:


  from bisect import bisect_right

  class Solution:
      def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:
          starts = sorted([start for start, _ in flowers])
          ends = sorted([end + 1 for _, end in flowers])
          m, n = len(flowers), len(people)
          ans = []

          for k in range(n):
              i = bisect_right(starts, people[k])
              j = bisect_right(ends, people[k])
              ans.append(i - j)

          return ans


_ Time Complexity:

  O((m + n) log(m)) - We preprocess m flowers and iterate through n people, executing binary search
  on m flowers for each person.

_ Space Complexity:

  O(m) - We store two arrays of m flower starts and ends.