We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Flowers in Full Bloom

Number: 2334

Difficulty: Hard

Paid? No

Companies: Roblox, Uber, Capital One, Databricks, Oracle, Google, Amazon, Microsoft, Samsara, Netflix

Problem Description

Given an array of flowers where each flower is represented by a start and end time indicating when it is in full bloom, and given an array of people arrival times, determine for each person how many flowers are in full bloom at the moment they arrive.

Key Insights

  • Instead of checking each flower for every person (which is inefficient), precompute and sort the start and end times of the flower intervals.
  • For each person's arrival time, count how many flowers have started blooming using binary search on the sorted start times.
  • Similarly, count how many flowers have finished blooming (end time less than the arrival time) using binary search on the sorted end times.
  • The difference gives the number of flowers in full bloom at that time.

Space and Time Complexity

Time Complexity: O((n + m) log n) where n is the number of flowers and m is the number of people. Space Complexity: O(n) for storing sorted start and end time arrays.

Solution

We use a binary search approach for efficiency. First, extract and sort the start times and end times from the flowers array. For each person's arrival time, use binary search to:

  • Find the count of flowers that have started blooming (using bisect_right or upper bound search on start times).
  • Find the count of flowers that have ended before the arrival time (using bisect_left or lower bound search on end times). Subtracting the second count from the first yields the number of flowers still in full bloom. This solution efficiently handles large inputs under the given constraints.

Code Solutions

import bisect

def fullBloomFlowers(flowers, people):
    # Extract start times and end times
    start_times = sorted([flower[0] for flower in flowers])
    end_times = sorted([flower[1] for flower in flowers])
    
    # List to store the result for each person's arrival time
    results = []
    
    # For each arrival time, count the number of flowers in full bloom
    for time in people:
        # Count of flowers that have started blooming <= time.
        count_started = bisect.bisect_right(start_times, time)
        # Count of flowers that have ended blooming < time.
        count_ended = bisect.bisect_left(end_times, time)
        # The number of flowers in bloom is the difference.
        results.append(count_started - count_ended)
    
    return results

# Example usage:
flowers = [[1,6],[3,7],[9,12],[4,13]]
people = [2,3,7,11]
print(fullBloomFlowers(flowers, people))  # Expected output: [1, 2, 2, 2]
← Back to All Questions