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.length1 <= n <= 10^51 <= plantTime[i], growTime[i] <= 10^4
Hints for Earliest Possible Day of Full Bloom
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.
Hint 2
The total planting time is fixed; what matters is which seed's growing overlaps with the rest of the work.
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
- Order the seeds by
growTime, largest first. - Walk that order keeping
planted, the days of work done so far: add the seed'splantTime, and its bloom day isplanted + growTime. - 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 bestJava
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