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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Flowers in Full Bloom

Difficulty: Hard

Problem Description

You are given a 0-indexed 2D integer array flowers, where flowers[i] = [start_i, end_i] means the i-th flower will be in full bloom from start_i to end_i (inclusive). You are also given a 0-indexed integer array people of size n, where people[i] is the time that the i-th 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 i-th person arrives.

Key Insights

  • Each flower has a specific blooming interval defined by its start and end times.
  • The task is to determine how many flowers are blooming at specific arrival times.
  • A direct approach would involve checking each flower for each person, which could lead to inefficient solutions.
  • Efficient strategies involve sorting or binary searching to minimize the checks needed for each query.

Space and Time Complexity

Time Complexity: O((m + n) log(m + n)), where m is the number of flowers and n is the number of people. This accounts for sorting the flowers and people arrays and performing binary searches to count blooms. Space Complexity: O(m + n) for storing the sorted arrays and results.

Solution

The solution uses sorting and binary search to efficiently count the number of flowers in bloom at each person's arrival time. The flowers are first processed to create a timeline of blooming intervals. For each person's arrival time, a binary search is performed to quickly determine how many flowers are blooming at that moment.

Code Solutions

def numFlowersInBloom(flowers, people):
    # Create a list of events for each flower's blooming period
    events = []
    for start, end in flowers:
        events.append((start, 1))  # Flower starts blooming
        events.append((end + 1, -1))  # Flower stops blooming (end + 1)
    
    # Sort events by time, and then by type of event (start before end)
    events.sort()
    
    # Prepare to count blooms
    current_bloom_count = 0
    bloom_counts = []
    idx = 0
    total_events = len(events)

    # Sort people's arrival times and keep track of original indices
    sorted_people = sorted((p, i) for i, p in enumerate(people))
    
    # Iterate through each person's arrival time
    for arrival_time, original_index in sorted_people:
        # Update bloom count based on events that have occurred by this arrival time
        while idx < total_events and events[idx][0] <= arrival_time:
            current_bloom_count += events[idx][1]
            idx += 1
        # Store the count of flowers in bloom at this arrival time
        bloom_counts.append((original_index, current_bloom_count))
    
    # Sort the results back to the original order of people's arrival times
    bloom_counts.sort()
    return [count for _, count in bloom_counts]
← Back to All Questions