Counting Full Bloom Flowers

Counting Full Bloom Flowers: An Efficient Algorithm

Problem Description

Given a list of flowers where each flower i has a blooming period represented by [start_i, end_i], and a list of people’s arrival times, determine how many flowers are in full bloom when each person arrives.

A flower is in full bloom at time t if start_i <= t <= end_i.

Intuition

The straightforward approach of checking each flower for each person would be too slow for large inputs (O(n*m)). Instead, we can use binary search to efficiently count the number of flowers that have started blooming by time t and subtract those that have already finished blooming.

Key Insight

For a flower to be in full bloom at time t:

1. It must have started blooming by time t (start_i ⇐ t)
2. It must not have finished blooming before time t (end_i >= t)

We can express this as:

flowers_in_bloom(t) = flowers_started_by(t) - flowers_ended_by(t)

Algorithm Explanation

1. Preprocessing:

   • Extract all start times into one list
   • Extract all end times into another list, adding 1 to each end time
   • Sort both lists

2. For each person’s arrival time:

   • Count flowers that started blooming by time t using binary search
   • Count flowers that finished blooming before time t using binary search
   • The difference gives the number of flowers in full bloom

Understanding bisect_right

bisect_right(arr, x) returns the insertion position where x would be placed in the sorted array arr to maintain sorted order, returning the position after any existing entries of x.

In simpler terms, it counts how many elements in the array are less than or equal to x.

Code Implementation

import bisect
from typing import List
 
class Solution:
    def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:
        starts = []
        ends = []
        
        # Extract start and end times
        for start, end in flowers:
            starts.append(start)
            ends.append(end + 1)  # Add 1 to mark when the flower stops blooming
            
        # Sort for binary search
        starts.sort()
        ends.sort()
        
        ans = []
        
        # For each person, count blooming flowers
        for person in people:
            # Count flowers that started blooming by person's arrival
            i = bisect.bisect_right(starts, person)
            # Count flowers that finished blooming before person's arrival
            j = bisect.bisect_right(ends, person)
            # Difference gives currently blooming flowers
            ans.append(i - j)
        
        return ans

Example Walkthrough

Let’s consider flowers [[1,3], [2,4]] and a person arriving at time 3:

1. Preprocessing:

   • Starts: [1, 2]
   • Ends: [4, 5] (3+1=4, 4+1=5)

2. Counting:

   • Flowers started by time 3: bisect_right([1,2], 3) = 2 (both started)
   • Flowers ended by time 3: bisect_right([4,5], 3) = 0 (none ended)
   • Result: 2 - 0 = 2 (both flowers are blooming)

Complexity Analysis

• Time Complexity: O((n + m) log n)
  • Sorting: O(n log n)
  • Binary searches: O(m log n)
• Space Complexity: O(n)
  • Storing start and end times

This approach efficiently solves the problem by leveraging binary search on pre-sorted arrays, making it suitable for large inputs.