Watch 10 video solutions for Earliest Possible Day of Full Bloom, a hard level problem involving Array, Greedy, Sorting. This walkthrough by codestorywithMIK has 8,934 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You have n flower seeds. Every seed must be planted first before it can begin to grow, then bloom. Planting a seed takes time and so does the growth of a seed. You are given two 0-indexed integer arrays plantTime and growTime, of length n each:
plantTime[i] is the number of full days it takes you to plant the ith seed. Every day, you can work on planting exactly one seed. You do not have to work on planting the same seed on consecutive days, but the planting of a seed is not complete until you have worked plantTime[i] days on planting it in total.growTime[i] is the number of full days it takes the ith seed to grow after being completely planted. After the last day of its growth, the flower blooms and stays bloomed forever.From the beginning of day 0, you can plant the seeds in any order.
Return the earliest possible day where all seeds are blooming.
Example 1:
Input: plantTime = [1,4,3], growTime = [2,3,1] Output: 9 Explanation: The grayed out pots represent planting days, colored pots represent growing days, and the flower represents the day it blooms. One optimal way is: On day 0, plant the 0th seed. The seed grows for 2 full days and blooms on day 3. On days 1, 2, 3, and 4, plant the 1st seed. The seed grows for 3 full days and blooms on day 8. On days 5, 6, and 7, plant the 2nd seed. The seed grows for 1 full day and blooms on day 9. Thus, on day 9, all the seeds are blooming.
Example 2:
Input: plantTime = [1,2,3,2], growTime = [2,1,2,1] Output: 9 Explanation: The grayed out pots represent planting days, colored pots represent growing days, and the flower represents the day it blooms. One optimal way is: On day 1, plant the 0th seed. The seed grows for 2 full days and blooms on day 4. On days 0 and 3, plant the 1st seed. The seed grows for 1 full day and blooms on day 5. On days 2, 4, and 5, plant the 2nd seed. The seed grows for 2 full days and blooms on day 8. On days 6 and 7, plant the 3rd seed. The seed grows for 1 full day and blooms on day 9. Thus, on day 9, all the seeds are blooming.
Example 3:
Input: plantTime = [1], growTime = [1] Output: 2 Explanation: On day 0, plant the 0th seed. The seed grows for 1 full day and blooms on day 2. Thus, on day 2, all the seeds are blooming.
Constraints:
n == plantTime.length == growTime.length1 <= n <= 1051 <= plantTime[i], growTime[i] <= 104Problem Overview: You are given two arrays: plantTime and growTime. Each seed must first be planted (taking plantTime[i] days) and then grows for growTime[i] days before blooming. Only one seed can be planted at a time, but multiple seeds can grow simultaneously. The goal is to schedule the planting order so that the last flower blooms as early as possible.
Approach 1: Shorter Plant Time Priority (Greedy with Sorting) (Time: O(n log n), Space: O(n))
This strategy sorts seeds by plantTime so the fastest planting tasks happen earlier. Iterate through the sorted seeds while maintaining a running sum of total planting days. After planting seed i, its bloom day becomes currentPlantDays + growTime[i]. Track the maximum bloom day across all seeds. The intuition is that quick planting steps allow you to start more growing phases sooner. Implementation uses arrays and a simple sorting step followed by a linear pass.
Approach 2: Long Grow Time Priority (Optimal Greedy) (Time: O(n log n), Space: O(n))
The key insight: seeds with the longest growTime should start growing as early as possible. Since growing happens in parallel but planting is sequential, delaying a long grow phase directly delays the final bloom day. Sort seeds in descending order of growTime. Then iterate through the order, accumulating planting days and computing the bloom day for each seed. Keep the maximum bloom day as the answer. This greedy strategy works because swapping a long-grow seed later in the order always increases the final completion time. The algorithm relies on greedy scheduling combined with sorting.
Recommended for interviews: The Long Grow Time Priority greedy approach is what most interviewers expect. It demonstrates scheduling intuition and the ability to reason about parallel vs sequential phases. Mentioning the alternative ordering shows exploration, but identifying that the longest grow tasks must start earliest shows strong problem-solving maturity.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Shorter Plant Time Priority | O(n log n) | O(n) | Useful as an intuitive starting point when exploring scheduling strategies |
| Long Grow Time Priority (Optimal Greedy) | O(n log n) | O(n) | General optimal solution; prioritize seeds with longest growth duration |