2136. Earliest Possible Day of Full Bloom

Problem Description

In this problem, you have n flower seeds that you need to plant and grow. Each flower seed has two associated times:

• plantTime[i]: This is the number of full days it takes to plant the i-th seed. You can only work on planting one seed per day, but you don't have to do it on consecutive days. However, you cannot consider a seed as planted until you've spent the total number of plantTime[i] days on it.

• growTime[i]: This is the number of full days it takes for the i-th seed to grow and bloom after it has been completely planted. Once a flower blooms, at the end of its growth time, it stays bloomed forever.

The task is to arrange your planting strategy to ensure that all the seeds are blooming by the earliest possible day. You can plant the seeds in any order starting from day 0.

Intuition

To solve the problem, the main insight is that seeds with a longer growth time ("growTime") should be prioritised for planting. This is because the growth process can occur simultaneously with the planting of other seeds. In other words, if a seed takes a long time to grow, you want to start that growth period as soon as possible, so it doesn't delay the point in time when all flowers are blooming.

Here is the step-by-step intuition for the solution:

1. Pair each seed's planting time with its growth time and consider these as a combined attribute of the seed.

2. Sort the seeds in descending order of their growth time. By doing this, we prioritize planting seeds with the longest growth time.

3. Initialize two variables, t and ans. t will keep track of the total time spent planting seeds up to the current seed, and ans will represent the earliest day all seeds are blooming. Start with both at zero.

4. Iterate through the sorted list of pairs:

   • Increment t by the current seed's planting time. This represents the day by which planting of this seed is finished.

   • Calculate the potential blooming day for the current seed by adding its growth time to t.

   • Update ans to be the maximum of its current value and the potential blooming day for the current seed. This ensures that ans always represents the day by which all seeds seen so far will have bloomed.

5. After the iteration, ans will contain the earliest possible day where all seeds are blooming by following the optimal planting order.

The logic behind this approach is that by focusing on getting the long-growth seeds growing as early as possible, you minimize the waiting time at the end of the planting schedule for the flowers to bloom.

Learn more about Greedy and Sorting patterns.

Solution Approach

To implement the solution, we utilize sorting and straightforward iteration to find the optimal sequence for planting the seeds.

• Sorting: We begin by pairing each plantTime with the corresponding growTime for each seed. Then, we sort the pairs based on growTime in descending order. This sorting places the seeds with the longest growth period first, which are the seeds we want to plant as soon as possible.

  1# Pseudocode for [Sorting](/problems/sorting_summary)
  2paired_times = zip(plantTime, growTime)
  3sorted_times = sorted(paired_times, key=lambda x: -x[1])

• Iteration: Next, we iterate through our sorted pairs and simulate the planting and growing process.

  1# Pseudocode for Iteration
  2t = 0 # Total days spent planting
  3ans = 0 # The earliest day all seeds are blooming
  4for pt, gt in sorted_times:
  5    t += pt # Increment total planting days by current seed's planting time
  6    ans = max(ans, t + gt) # Update ans to the max of current ans and the potential bloom day

  • During each step, we adjust our t value by adding the current seed's planting time. This t represents the time passed solely due to planting activities.

  • We then consider the total time until the current seed blooms, which is t + gt (gt - growth time for the current seed). Since growth occurs after planting, it makes sense to sum these up.

  • The ans value is updated to ensure it represents the day when each seed planted so far will have bloomed. By using the max function, we ensure that it reflects the latest bloom amongst all seeds considered.

• Variables: Two key variables are used:

  • t: Tracks the cumulative days spent on planting.
  • ans: Tracks the earliest possible day where all seeds are blooming.

• Return Value: After the loop completes, ans represents the earliest day by which all the seeds would have bloomed. We arrived at this number by iteratively keeping track of the maximal end date for the blooming of each seed, hence considering the fact that while one seed is growing, we could be planting another.

The code demonstrates proper utilization of Python's list operations, such as zipping, sorting, and iteration. Moreover, the use of a simple max function elegantly resolves the problem of comparing bloom times and determining the overall earliest bloom day.

1# Reference Solution Code
2class Solution:
3    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:
4        ans = t = 0
5        for pt, gt in sorted(zip(plantTime, growTime), key=lambda x: -x[1]):
6            t += pt # day when planting of this seed is finished
7            ans = max(ans, t + gt) # latest bloom day amongst all seeds
8        return ans # the earliest possible day where all seeds are blooming

In the provided algorithm, each step is purposeful and designed to optimize the bloom time based on seed growth characteristics. By focusing on the growth period and organizing the planting schedule accordingly, we reach an optimal and efficient solution.

Example Walkthrough

Let's consider a small example to illustrate the solution approach:

Suppose we are given the following plantTime and growTime for n = 3 seeds:

• Seed 1: plantTime[0] = 1, growTime[0] = 4
• Seed 2: plantTime[1] = 2, growTime[1] = 3
• Seed 3: plantTime[2] = 3, growTime[2] = 2

Following the solution approach:

1. Pair each seed's planting time with its growth time:

1Seed 1 -> (1, 4)
2Seed 2 -> (2, 3)
3Seed 3 -> (3, 2)

2. Sort the seeds in descending order of grow time:

1Sorted Pairs: 
2  Seed 1 -> (1, 4)
3  Seed 2 -> (2, 3)
4  Seed 3 -> (3, 2)

(Note: Since our example is already in descending order, no changes are made).

3. Initialize t and ans to zero:

1t = 0 (Total days spent planting)
2ans = 0 (Earliest day all seeds are blooming)

4. Iterate through the sorted list of pairs:

• For Seed 1: pt = 1, gt = 4

1t += 1 (t = 1) 
2ans = max(ans, t + gt) = max(0, 1 + 4) = 5

• For Seed 2: pt = 2, gt = 3

1t += 2 (t = 3)
2ans = max(ans, t + gt) = max(5, 3 + 3) = 6

• For Seed 3: pt = 3, gt = 2

1t += 3 (t = 6)
2ans = max(ans, t + gt) = max(6, 6 + 2) = 8

5. At the end of the iteration, ans is 8, which means all seeds will be blooming by day 8.

In this example, prioritizing the planting of seeds with the largest growTime allowed the seeds to start growing earlier. Even though seeds with shorter plantTime could have been planted first, since we prioritize by growTime, we minimize the overall waiting for flowers to bloom. Thus, following the optimal planting order, all seeds will be blooming by day 8.

Solution Implementation

Time and Space Complexity

The given Python function earliestFullBloom calculates the earliest day on which all plants will be in full bloom. It does so by first sorting the combined planting and growing times in descending order of growing time, then iterating through them to calculate the total time required.

Time Complexity

The time complexity of the function is determined by the sorted function and the subsequent iteration through the sorted list.

1. Sorting the zipped list sorted(zip(plantTime, growTime), key=lambda x: -x[1]) has a time complexity of O(n log n), where n represents the number of elements in plantTime or growTime lists.
2. The following for loop iterates through each element once, which has a time complexity of O(n).

Combining these two steps, the overall time complexity is dominated by the sorting step, making it O(n log n).

Space Complexity

The space complexity of the function is determined by the additional space used by the sorted list and the variables inside the function.

1. The sorted list creates a new list of pairs from plantTime and growTime, having space complexity O(n).
2. Variables ans, t, pt, and gt use constant space O(1).

Hence, the total space complexity of the function is O(n) for storing the sorted list.

Learn more about how to find time and space complexity quickly using problem constraints.