Problem Description

You have information about when flowers bloom and when people arrive to see them.

Given:

• A 2D array flowers where each flowers[i] = [start_i, end_i] represents that the i-th flower blooms from day start_i to day end_i (both days inclusive)
• An array people where people[i] represents the day when the i-th person arrives

You need to find out how many flowers are in full bloom when each person arrives.

For example, if a flower blooms from day 3 to day 7, and a person arrives on day 5, that flower would be counted as blooming for that person. If another flower blooms from day 1 to day 4, it would not be counted for this person since it has already wilted by day 5.

The solution uses a clever approach:

1. Create two sorted lists: one with all bloom start times and one with all bloom end times
2. For each person arriving at time p:
   • Count how many flowers have started blooming by time p using bisect_right(start, p)
   • Count how many flowers have already finished blooming before time p using bisect_left(end, p)
   • The difference gives the number of flowers currently in bloom

The key insight is that bisect_right(start, p) counts all flowers that started at or before time p, while bisect_left(end, p) counts all flowers that ended strictly before time p. The difference between these two values gives the exact count of flowers blooming at time p.

Intuition

Think about what it means for a flower to be blooming at a specific time. A flower is blooming at time t if:

• It has already started blooming (its start time ≤ t)
• It hasn't finished blooming yet (its end time ≥ t)

This naturally leads us to think about counting flowers in two groups:

1. Flowers that have started by time t
2. Flowers that have ended before time t

The number of flowers blooming at time t = (flowers that have started) - (flowers that have already ended)

Instead of checking each flower individually for each person (which would be inefficient), we can preprocess the data. By separating all start times and end times into two sorted arrays, we can quickly answer "how many flowers have started/ended by time t" using binary search.

The trick with using bisect_right for starts and bisect_left for ends handles the boundary cases correctly:

• bisect_right(start, p) counts all flowers where start_time <= p
• bisect_left(end, p) counts all flowers where end_time < p

This is important because a flower that ends on day p should still be counted as blooming on day p (since the end time is inclusive). By using bisect_left for end times, we only exclude flowers that ended strictly before day p.

This transforms a potentially complex interval overlap problem into a simple counting problem using sorted arrays and binary search, achieving an efficient solution.

Learn more about Binary Search, Prefix Sum and Sorting patterns.

Solution Approach

The solution implements the sorting and binary search strategy to efficiently count blooming flowers for each person.

Step 1: Extract and Sort Start/End Times

start, end = sorted(a for a, _ in flowers), sorted(b for _, b in flowers)

• Extract all start times from flowers array and sort them: start = [start_1, start_2, ..., start_n]
• Extract all end times from flowers array and sort them: end = [end_1, end_2, ..., end_n]
• Sorting enables binary search for efficient lookups

Step 2: Calculate Blooming Flowers for Each Person

return [bisect_right(start, p) - bisect_left(end, p) for p in people]

For each person arriving at time p:

1. Count flowers that have started blooming:

   • bisect_right(start, p) returns the position where p would be inserted to keep the array sorted, counting from the right
   • This gives us the count of all flowers where start_time <= p
   • For example, if start = [1, 3, 5, 7] and p = 4, bisect_right returns 2 (flowers starting at times 1 and 3)

2. Count flowers that have finished blooming:

   • bisect_left(end, p) returns the position where p would be inserted to keep the array sorted, counting from the left
   • This gives us the count of all flowers where end_time < p
   • For example, if end = [2, 4, 6, 8] and p = 4, bisect_left returns 1 (only the flower ending at time 2 has finished)

3. Calculate the difference:

   • bisect_right(start, p) - bisect_left(end, p) gives the number of flowers currently blooming
   • This works because flowers blooming at time p are those that have started but haven't ended yet

Time Complexity: O((m + n) log m) where m is the number of flowers and n is the number of people

• Sorting takes O(m log m)
• Each binary search takes O(log m), performed n times

Space Complexity: O(m) for storing the sorted start and end arrays

Example Walkthrough

Let's walk through a concrete example to understand how the solution works.

Given:

• flowers = [[1,6], [3,7], [9,12], [4,13]]
• people = [2, 3, 7, 11]

Step 1: Extract and sort start/end times

From the flowers array, we extract:

• Start times: [1, 3, 9, 4] → Sorted: [1, 3, 4, 9]
• End times: [6, 7, 12, 13] → Sorted: [6, 7, 12, 13]

Step 2: Process each person

For person at day 2:

• bisect_right(start=[1,3,4,9], p=2) = 1
  • Only flower starting at day 1 has begun (1 ≤ 2)
• bisect_left(end=[6,7,12,13], p=2) = 0
  • No flowers have ended yet (no end times < 2)
• Blooming flowers: 1 - 0 = 1

For person at day 3:

• bisect_right(start=[1,3,4,9], p=3) = 2
  • Flowers starting at days 1 and 3 have begun (both ≤ 3)
• bisect_left(end=[6,7,12,13], p=3) = 0
  • No flowers have ended yet (no end times < 3)
• Blooming flowers: 2 - 0 = 2

For person at day 7:

• bisect_right(start=[1,3,4,9], p=7) = 3
  • Flowers starting at days 1, 3, and 4 have begun (all ≤ 7)
• bisect_left(end=[6,7,12,13], p=7) = 1
  • Only the flower ending at day 6 has finished (6 < 7)
  • Note: The flower ending at day 7 is still blooming!
• Blooming flowers: 3 - 1 = 2

For person at day 11:

• bisect_right(start=[1,3,4,9], p=11) = 4
  • All flowers have started (all start times ≤ 11)
• bisect_left(end=[6,7,12,13], p=11) = 2
  • Flowers ending at days 6 and 7 have finished (both < 11)
• Blooming flowers: 4 - 2 = 2

Result: [1, 2, 2, 2]

The key insight is how bisect_left for end times ensures flowers ending on the same day as a person's arrival are still counted as blooming, while bisect_right for start times includes flowers that start on the arrival day.

Solution Implementation

Time and Space Complexity

Time Complexity: O((m + n) × log n)

The time complexity breaks down as follows:

• Sorting the start times: O(n log n) where n is the number of flowers
• Sorting the end times: O(n log n) where n is the number of flowers
• For each person in people, we perform:
  • bisect_right(start, p): O(log n) binary search
  • bisect_left(end, p): O(log n) binary search
  • Since there are m people, this step takes O(m × log n)
• Total: O(n log n + n log n + m × log n) = O((m + n) × log n)

Space Complexity: O(n)

The space complexity consists of:

• start array: O(n) space to store all flower start times
• end array: O(n) space to store all flower end times
• The result list uses O(m) space but is not counted as auxiliary space since it's the output
• Total auxiliary space: O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Confusing bisect_left and bisect_right usage

The most critical pitfall is incorrectly using bisect_left and bisect_right, which leads to off-by-one errors in counting blooming flowers.

Incorrect Implementation:

# WRONG: Using bisect_left for both or swapping them
flowers_started = bisect_left(bloom_starts, arrival_time)  # Misses flowers starting exactly at arrival_time
flowers_ended = bisect_right(bloom_ends, arrival_time)     # Counts flowers ending at arrival_time as already ended

Why this fails:

• If a flower starts exactly at the arrival time, it should be counted as blooming
• If a flower ends exactly at the arrival time, it should still be counted as blooming (inclusive end time)
• Using bisect_left for starts would miss flowers that begin exactly when the person arrives
• Using bisect_right for ends would incorrectly exclude flowers that end on the arrival day

Correct Implementation:

# RIGHT: bisect_right for starts, bisect_left for ends
flowers_started = bisect_right(bloom_starts, arrival_time)  # Counts all flowers with start_time <= arrival_time
flowers_ended = bisect_left(bloom_ends, arrival_time)       # Counts all flowers with end_time < arrival_time

2. Not handling the inclusive nature of bloom periods

Another pitfall is forgetting that bloom periods are inclusive on both ends.

Example scenario:

• Flower blooms from day 3 to day 5 (inclusive)
• Person arrives on day 5
• The flower should be counted as blooming

Test case to validate:

flowers = [[3, 5], [1, 2]]
people = [5, 2]
# Expected output: [1, 1]
# Day 5: Only flower [3, 5] is blooming
# Day 2: Only flower [1, 2] is blooming

3. Memory inefficiency with the compact one-liner

While the one-liner solution is elegant, it can be less memory efficient:

Potentially inefficient:

# Creates intermediate lists in memory
start, end = sorted(a for a, _ in flowers), sorted(b for _, b in flowers)

More memory-efficient alternative:

# Extracts values more directly
start = sorted([flower[0] for flower in flowers])
end = sorted([flower[1] for flower in flowers])

4. Not considering edge cases

Edge cases to handle:

• Empty flowers array: Should return all zeros
• Single-day bloom periods: Where start_time equals end_time
• Overlapping bloom periods: Multiple flowers blooming at the same time

Robust solution with edge case handling:

def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:
    # Handle empty flowers array
    if not flowers:
        return [0] * len(people)
  
    bloom_starts = sorted(start for start, _ in flowers)
    bloom_ends = sorted(end for _, end in flowers)
  
    result = []
    for arrival_time in people:
        flowers_started = bisect_right(bloom_starts, arrival_time)
        flowers_ended = bisect_left(bloom_ends, arrival_time)
        result.append(flowers_started - flowers_ended)
  
    return result