Number of Flowers in Full Bloom

Hard
1381.

Number of Flowers in Full Bloom

Number of Flowers in Full Bloom is a hard coding problem on arrays, sorting and binary search, asked in Amazon, Google, Meta and Databricks interviews.

A garden has flowers whose blooming windows are given as flowers[i] = [start_i, end_i]: flower i is in full bloom at every time t with start_i <= t <= end_i (both ends inclusive).

Visitors arrive at the times in people; visitor j arrives at people[j].

Return an array answer of the same length as people, where answer[j] is the number of flowers in full bloom when visitor j arrives.

Example 1

Input
flowers = [[1,6],[3,7],[9,12],[4,13]], people = [2,3,7,11]
Output
[1,2,2,2]
Explanation
At time 7 the flowers [3,7] and [4,13] bloom; [1,6] has just ended.

Example 2

Input
flowers = [[1,10],[3,3]], people = [3,3,2]
Output
[2,2,1]

Constraints

  • 1 <= flowers.length <= 5 * 10^4
  • flowers[i].length == 2
  • 1 <= start_i <= end_i <= 10^9
  • 1 <= people.length <= 5 * 10^4
  • 1 <= people[j] <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} flowers
 * @param {number[]} people
 * @return {number[]}
 */
var fullBloomFlowers = function(flowers, people) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Flowers in Full Bloom — Problem & Solution

Number of Flowers in Full Bloom solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Number of Flowers in Full Bloom is a hard coding problem on arrays, sorting and binary search, asked in Amazon, Google, Meta and Databricks interviews.

Problem statement

A garden has flowers whose blooming windows are given as flowers[i] = [start_i, end_i]: flower i is in full bloom at every time t with start_i <= t <= end_i (both ends inclusive).

Visitors arrive at the times in people; visitor j arrives at people[j].

Return an array answer of the same length as people, where answer[j] is the number of flowers in full bloom when visitor j arrives.

Example 1

Input: flowers = [[1,6],[3,7],[9,12],[4,13]], people = [2,3,7,11]
Output: [1,2,2,2]
Explanation: At time 7 the flowers [3,7] and [4,13] bloom; [1,6] has just ended.

Example 2

Input: flowers = [[1,10],[3,3]], people = [3,3,2]
Output: [2,2,1]

Constraints

  • 1 <= flowers.length <= 5 * 10^4
  • flowers[i].length == 2
  • 1 <= start_i <= end_i <= 10^9
  • 1 <= people.length <= 5 * 10^4
  • 1 <= people[j] <= 10^9

Hints for Number of Flowers in Full Bloom

  1. Hint 1

    A flower blooms at time t exactly when it has started by t and has not ended before t.

  2. Hint 2

    So the count at t is (number of starts <= t) minus (number of ends < t) — every flower that ended before t had also started.

  3. Hint 3

    Sort the start times and the end times separately; each of the two counts is one binary search.

How to solve Number of Flowers in Full Bloom

Split the intervals into two sorted lists — starts and ends. The number of flowers blooming at t equals the starts at or before t minus the ends strictly before t, and both counts are binary searches.

Approach

  1. Copy all start_i into one array and all end_i into another; sort both.
  2. For each arrival t, let started = number of starts <= t (upper bound of t).
  3. Let ended = number of ends < t (lower bound of t).
  4. The answer for that visitor is started - ended.

Why it works

Every flower with end < t also has start <= end < t, so it is counted in started. Subtracting those leaves exactly the flowers with start <= t <= end. Because the two lists are sorted, the counts are the insertion points found by binary search.

Complexity

  • Time — O((f + p) log f)
  • Space — O(f)

Pitfalls

  • The bloom window is inclusive at both ends — ends count as < t, starts as <= t.
  • Visitors are not sorted; answer them in input order.
  • A sweep over sorted events also works, but needs the visitors sorted with their indices kept.

Reference solution

Python

from typing import List
import bisect

def fullBloomFlowers(flowers: List[List[int]], people: List[int]) -> List[int]:
    starts = sorted(f[0] for f in flowers)
    ends = sorted(f[1] for f in flowers)
    return [bisect.bisect_right(starts, t) - bisect.bisect_left(ends, t) for t in people]

Java

public static int[] fullBloomFlowers(int[][] flowers, int[] people) {
    int f = flowers.length;
    int[] starts = new int[f], ends = new int[f];
    for (int i = 0; i < f; i++) { starts[i] = flowers[i][0]; ends[i] = flowers[i][1]; }
    Arrays.sort(starts);
    Arrays.sort(ends);
    int[] res = new int[people.length];
    for (int j = 0; j < people.length; j++) {
        res[j] = firstIndexAbove(starts, people[j], true) - firstIndexAbove(ends, people[j], false);
    }
    return res;
}

static int firstIndexAbove(int[] a, int t, boolean strict) {
    int lo = 0, hi = a.length;
    while (lo < hi) {
        int mid = (lo + hi) >>> 1;
        if (strict ? a[mid] <= t : a[mid] < t) lo = mid + 1; else hi = mid;
    }
    return lo;
}

C++

vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& people) {
    vector<int> starts, ends;
    for (auto& f : flowers) { starts.push_back(f[0]); ends.push_back(f[1]); }
    sort(starts.begin(), starts.end());
    sort(ends.begin(), ends.end());
    vector<int> res;
    for (int t : people) {
        int started = upper_bound(starts.begin(), starts.end(), t) - starts.begin();
        int ended = lower_bound(ends.begin(), ends.end(), t) - ends.begin();
        res.push_back(started - ended);
    }
    return res;
}

JavaScript

var fullBloomFlowers = function(flowers, people) {
    var starts = [], ends = [];
    for (var i = 0; i < flowers.length; i++) {
        starts.push(flowers[i][0]);
        ends.push(flowers[i][1]);
    }
    var asc = function(a, b) { return a - b; };
    starts.sort(asc);
    ends.sort(asc);
    var firstAbove = function(a, t, strict) {
        var lo = 0, hi = a.length;
        while (lo < hi) {
            var mid = (lo + hi) >> 1;
            if (strict ? a[mid] <= t : a[mid] < t) lo = mid + 1; else hi = mid;
        }
        return lo;
    };
    var res = [];
    for (var j = 0; j < people.length; j++) {
        var t = people[j];
        res.push(firstAbove(starts, t, true) - firstAbove(ends, t, false));
    }
    return res;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms