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.
In this approach, we prioritize seeds with shorter planting times first. The idea is that we can start planting these seeds earlier, and consequently, they will finish blooming earlier. This might minimize the delay caused by longer-growing seeds.
This solution defines a structure for seeds, sorts them based on planting time, and calculates when all flowers will bloom.
Time Complexity: O(n log n) due to sorting. Space Complexity: O(n) for storing seeds in an array.
This strategy focuses on seeds with longer grow times first. By doing so, we minimize delays caused by excessively long growing periods by ensuring they finish growing as soon as possible.
This solution focuses on sorting the seeds based on maximum grow time first.
This helps accommodate delays caused by these seeds. It updates the potential maximum bloom day accordingly.
Time Complexity: O(n log n) because of sorting operations. Space Complexity: O(n) for storing seed data.
According to the problem description, we know that only one seed can be planted per day. Therefore, regardless of the planting order, the sum of the planting times for all seeds is always equal to sum_{i=0}^{n-1} plantTime[i]. To make all seeds bloom as soon as possible, we should prioritize planting the seeds with the longest growth time. Hence, we can sort all seeds by their growth time in descending order and then plant them in sequence.
The time complexity is O(n log n), and the space complexity is O(n), where n is the number of seeds.
| Approach | Complexity |
|---|---|
| Shorter Plant Time Priority | Time Complexity: O(n log n) due to sorting. Space Complexity: O(n) for storing seeds in an array. |
| Long Grow Time Priority | Time Complexity: O(n log n) because of sorting operations. Space Complexity: O(n) for storing seed data. |
| Greedy + Sorting | — |
| 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 |
Earliest Possible Day of Full Bloom(Google, Amazon, Microsoft, Adobe):Explanation ➕ Live Coding • codestorywithMIK • 8,934 views views
Watch 9 more video solutions →Practice Earliest Possible Day of Full Bloom with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor