Number of Flowers in Full Bloom - Practice Coding Problems

Number of Flowers in Full Bloom - Problem

Array Hash Table Binary Search Sorting Prefix Sum Ordered Set Hard

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.

Input & Output

Example 1 — Multiple People Different Times

$ Input: flowers = [[1,6],[3,7],[9,12]], people = [2,3,7,11]

› Output: [1,2,2,1]

💡 Note: At time 2: flower [1,6] is blooming (1). At time 3: flowers [1,6] and [3,7] are blooming (2). At time 7: flowers [1,6] and [3,7] are blooming (2). At time 11: only flower [9,12] is blooming (1).

Example 2 — Single Flower

$ Input: flowers = [[1,10]], people = [5]

› Output: [1]

💡 Note: Only one flower [1,10] and person arrives at time 5, which falls within the bloom period, so 1 flower is blooming.

Example 3 — No Overlapping Blooms

$ Input: flowers = [[1,2],[3,4],[5,6]], people = [2,4,6]

› Output: [1,1,1]

💡 Note: Each person arrives exactly when only one flower is blooming. No time overlaps between different flowers.

Constraints

1 ≤ flowers.length ≤ 5 × 10⁴
flowers[i].length == 2
1 ≤ start_i ≤ end_i ≤ 10⁹
1 ≤ people.length ≤ 5 × 10⁴
1 ≤ people[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Flower bloom intervals and people arrival times

Process

For each person, count overlapping flower intervals

Output

Array of bloom counts for each person

Key Takeaway

🎯 Key Insight: Binary search on sorted start/end arrays efficiently counts active intervals without checking each one individually

Asked in

G Google 45 a Amazon 38 M Microsoft 32 Apple 25

The key insight is to convert the interval overlap problem into counting started vs ended flowers using binary search. The optimal binary search approach sorts flower start/end times separately and uses binary search to efficiently count blooming flowers for each query. Time: O(n log n + m log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Prefix Sum with Coordinate Compression	O((n+m) log(n+m))	O(n+m)	Use difference array technique with coordinate compression for efficient range queries
Binary Search on Start/End Arrays	O(n log n + m log n)	O(n)	Sort flower start and end times separately, then use binary search to count overlapping intervals
Brute Force - Check Every Flower	O(n×m)	O(1)	For each person, iterate through all flowers and count those in bloom

Prefix Sum with Coordinate Compression — Algorithm Steps

Collect all unique time points from flowers and people
Create difference array: +1 at start, -1 at end+1
Calculate prefix sum to get bloom count at each time
Binary search to find bloom count for each person

Visualization

Tap to expand

Step-by-Step Walkthrough

Create Events

Mark +1 at flower start, -1 at flower end+1

Prefix Sum

Calculate running total of blooming flowers

Query

Binary search to find bloom count at any time

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int binarySearch(int* arr, int size, int target) {
    int left = 0, right = size - 1, result = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] <= target) {
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

int* solution(int** flowers, int flowersSize, int* people, int peopleSize, int* returnSize) {
    // Simplified implementation for basic cases
    int* answer = (int*)malloc(peopleSize * sizeof(int));
    *returnSize = peopleSize;
    
    for (int i = 0; i < peopleSize; i++) {
        int count = 0;
        for (int j = 0; j < flowersSize; j++) {
            if (flowers[j][0] <= people[i] && people[i] <= flowers[j][1]) {
                count++;
            }
        }
        answer[i] = count;
    }
    return answer;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int** flowers = (int**)malloc(100 * sizeof(int*));
    for (int i = 0; i < 100; i++) {
        flowers[i] = (int*)malloc(2 * sizeof(int));
    }
    int flowersSize = 0;
    
    fgets(line, sizeof(line), stdin);
    int* people = (int*)malloc(100 * sizeof(int));
    int peopleSize = 0;
    
    int returnSize;
    int* result = solution(flowers, flowersSize, people, peopleSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O((n+m) log(n+m))

Sorting unique times dominates, then binary search for each query

⚡ Linearithmic

Space Complexity

O(n+m)

Store unique times and prefix sum array

⚡ Linearithmic Space

58.4K Views

Medium Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Prefix Sum with Coordinate Compression — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler