Earliest Possible Day of Full Bloom

Hard
1432.

Earliest Possible Day of Full Bloom

Earliest Possible Day of Full Bloom is a hard coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.

You have n flower seeds. Seed i needs plantTime[i] full days of planting work — the days need not be consecutive, but you can work on only one seed per day. Once its planting is finished, it grows for growTime[i] full days and blooms at the end of the last one; a bloomed flower stays in bloom forever.

Starting on day 0, choose the order of the work. Return the earliest day on which every seed is blooming.

In other words, if seed i's planting finishes after P days of work in total, it blooms on day P + growTime[i]; the answer is the smallest possible maximum of those days.

Example 1

Input
plantTime = [2,1,3], growTime = [1,5,2]
Output
7
Explanation
Plant seed 1 (done after 1 day, blooms day 6), then seed 2 (done after 4, blooms 6), then seed 0 (done after 6, blooms 7).

Example 2

Input
plantTime = [1,2,3,2], growTime = [2,1,2,1]
Output
9

Example 3

Input
plantTime = [1], growTime = [1]
Output
2

Constraints

  • n == plantTime.length == growTime.length
  • 1 <= n <= 10^5
  • 1 <= plantTime[i], growTime[i] <= 10^4
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[]} plantTime
 * @param {number[]} growTime
 * @return {number}
 */
var earliestFullBloom = function(plantTime, growTime) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Earliest Possible Day of Full Bloom — Problem & Solution

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

Earliest Possible Day of Full Bloom is a hard coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.

  • Difficulty: Hard
  • Topics: Arrays, Sorting, Greedy
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You have n flower seeds. Seed i needs plantTime[i] full days of planting work — the days need not be consecutive, but you can work on only one seed per day. Once its planting is finished, it grows for growTime[i] full days and blooms at the end of the last one; a bloomed flower stays in bloom forever.

Starting on day 0, choose the order of the work. Return the earliest day on which every seed is blooming.

In other words, if seed i's planting finishes after P days of work in total, it blooms on day P + growTime[i]; the answer is the smallest possible maximum of those days.

Example 1

Input: plantTime = [2,1,3], growTime = [1,5,2]
Output: 7
Explanation: Plant seed 1 (done after 1 day, blooms day 6), then seed 2 (done after 4, blooms 6), then seed 0 (done after 6, blooms 7).

Example 2

Input: plantTime = [1,2,3,2], growTime = [2,1,2,1]
Output: 9

Example 3

Input: plantTime = [1], growTime = [1]
Output: 2

Constraints

  • n == plantTime.length == growTime.length
  • 1 <= n <= 10^5
  • 1 <= plantTime[i], growTime[i] <= 10^4

Hints for Earliest Possible Day of Full Bloom

  1. Hint 1

    Splitting a seed's planting across non-consecutive days never helps: finishing one seed before starting the next blooms everything at least as early.

  2. Hint 2

    The total planting time is fixed; what matters is which seed's growing overlaps with the rest of the work.

  3. Hint 3

    Plant the seeds in decreasing order of growTime — the slowest growers should start growing first.

How to solve Earliest Possible Day of Full Bloom

All planting takes the same total time whatever the order, so the question is only which seeds finish planting late. A seed that grows quickly can afford to be planted last; a slow grower must be planted early. Sorting by growTime descending is optimal.

Approach

  1. Order the seeds by growTime, largest first.
  2. Walk that order keeping planted, the days of work done so far: add the seed's plantTime, and its bloom day is planted + growTime.
  3. Return the maximum bloom day seen.

Why it works

Take any order with two adjacent seeds a then b where growTime[a] < growTime[b], and let P be the planting work done when the second of them finishes. Before the swap b blooms on day P + growTime[b]. After it, b finishes earlier and blooms by P - plantTime[a] + growTime[b], and a blooms on P + growTime[a] — both at most P + growTime[b]. Every other seed is unaffected, so the swap never makes the answer worse, and repeated swaps reach the descending order.

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • Sorting by plantTime (shortest job first) is the classic wrong guess — it ignores growing entirely.
  • The bloom day uses the cumulative planting time including this seed.
  • With the full limits the cumulative planting time reaches 10^9, still within 32 bits, but only just.

Reference solution

Python

from typing import List

def earliestFullBloom(plantTime: List[int], growTime: List[int]) -> int:
    order = sorted(range(len(plantTime)), key=lambda i: -growTime[i])
    planted = best = 0
    for i in order:
        planted += plantTime[i]
        best = max(best, planted + growTime[i])
    return best

Java

public static int earliestFullBloom(int[] plantTime, int[] growTime) {
    int n = plantTime.length;
    Integer[] order = new Integer[n];
    for (int i = 0; i < n; i++) order[i] = i;
    Arrays.sort(order, (a, b) -> Integer.compare(growTime[b], growTime[a]));
    int planted = 0, best = 0;
    for (int i : order) {
        planted += plantTime[i];
        best = Math.max(best, planted + growTime[i]);
    }
    return best;
}

C++

int earliestFullBloom(vector<int>& plantTime, vector<int>& growTime) {
    int n = plantTime.size();
    vector<int> order(n);
    for (int i = 0; i < n; i++) order[i] = i;
    sort(order.begin(), order.end(), [&](int a, int b) { return growTime[a] > growTime[b]; });
    int planted = 0, best = 0;
    for (int i : order) {
        planted += plantTime[i];
        best = max(best, planted + growTime[i]);
    }
    return best;
}

JavaScript

var earliestFullBloom = function(plantTime, growTime) {
    var order = [];
    for (var i = 0; i < plantTime.length; i++) order.push(i);
    order.sort(function(a, b) { return growTime[b] - growTime[a]; });
    var planted = 0, best = 0;
    for (var t = 0; t < order.length; t++) {
        planted += plantTime[order[t]];
        best = Math.max(best, planted + growTime[order[t]]);
    }
    return best;
};

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