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] <= 104In 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) because of sorting operations. Space Complexity: O(n) for storing seed data.
| 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. |
Earliest Possible Day of full bloom || LeetCode 2136 || Weekly LeetCode 275 || Greedy || Hard || C++ • Bro Coders • 2,384 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