Earliest Possible Day of Full Bloom
Hard
You are given 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 thei<sup>th</sup>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 workedplantTime[i]days on planting it in total.growTime[i]is the number of full days it takes thei<sup>th</sup>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:
plantTime = [1,4,3], growTime = [2,3,1]
Output: 9
Example 2:
plantTime = [1,2,3,2], growTime = [2,1,2,1]
Output: 9
Example 3:
plantTime = [1], growTime = [1]
Output: 2
Explain how to solve this problem optimally and provide code. Consider edge cases and analyze space and time complexity.
Solution
Naive Solution
A brute-force solution would involve trying all possible permutations of planting the seeds and calculating the bloom day for each permutation. We then return the minimum bloom day across all permutations.
Code (Python)
import itertools
def earliest_bloom_naive(plantTime, growTime):
n = len(plantTime)
min_bloom_day = float('inf')
for permutation in itertools.permutations(range(n)):
current_plant_day = 0
max_bloom_day = 0
for i in permutation:
current_plant_day += plantTime[i]
bloom_day = current_plant_day + growTime[i]
max_bloom_day = max(max_bloom_day, bloom_day)
min_bloom_day = min(min_bloom_day, max_bloom_day)
return min_bloom_day
Time Complexity
The time complexity is O(n! * n), where n! is the number of permutations and O(n) is the time to calculate the bloom day for each permutation.
Space Complexity
The space complexity is O(n) due to the storage of the permutation.
Optimal Solution
The optimal solution is based on a greedy approach. The key insight is that seeds with longer grow times should be planted earlier. This minimizes the overall bloom time.
Algorithm
- Create a list of seed indices.
- Sort the seed indices in descending order based on their
growTime. - Iterate through the sorted seed indices and calculate the bloom day.
- Return the maximum bloom day.
Code (Python)
def earliest_bloom(plantTime, growTime):
n = len(plantTime)
seeds = sorted(range(n), key=lambda i: growTime[i], reverse=True)
current_plant_day = 0
max_bloom_day = 0
for i in seeds:
current_plant_day += plantTime[i]
bloom_day = current_plant_day + growTime[i]
max_bloom_day = max(max_bloom_day, bloom_day)
return max_bloom_day
Time Complexity
The time complexity is dominated by the sorting step, which is O(n log n).
Space Complexity
The space complexity is O(n) to store the seed indices.
Edge Cases
- Empty Input: If either
plantTimeorgrowTimeare empty, it should return 0 (or handle the exception appropriately). - Single Seed: If there's only one seed, the bloom day is simply
plantTime[0] + growTime[0]. - Large Values: Ensure that the intermediate calculations don't overflow, especially with very large
plantTimeorgrowTimevalues.
