Skip to main content
Talentd

Earliest Possible Day of Full Bloom - Solution & Explanation

HardArrayGreedySorting17 min readAsked at: Visa
Practice this problem

Problem Statement

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.length
  • 1 <= n <= 105
  • 1 <= plantTime[i], growTime[i] <= 104

Approach Overview

Problem 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 1: Shorter Plant Time Priority

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting. Space Complexity: O(n) for storing seeds in an array.

Try this approach in the editor →

Approach 2: Long Grow Time Priority

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) because of sorting operations. Space Complexity: O(n) for storing seed data.

Try this approach in the editor →

Approach 3: Greedy + Sorting

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Shorter Plant Time PriorityO(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

Video Solution

Earliest Possible Day of Full Bloom(Google, Amazon, Microsoft, Adobe):Explanation ➕ Live Coding • codestorywithMIK • 10,174 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Earliest Possible Day of Full Bloom easy or hard?
The problem is labeled Hard because the correct greedy insight is not immediately obvious. Many initial attempts focus on plantTime ordering, but the key observation is that long grow times must start earlier. Once that insight is identified, the implementation is straightforward.
Earliest Possible Day of Full Bloom Python/Java solution
In Python or Java, create pairs of plantTime and growTime, sort them by growTime descending, and iterate through the list. Maintain a running planting total and compute bloomDay = currentPlantDays + growTime for each seed. Track the maximum bloom day to return the earliest day when all flowers bloom.
How to solve Earliest Possible Day of Full Bloom in O(n)?
An exact optimal solution generally requires sorting, which makes the time complexity O(n log n). Achieving strict O(n) would require bounded growTime values enabling counting sort or bucket sort. In typical implementations, the greedy sorting approach is considered optimal.
What is the best approach for Earliest Possible Day of Full Bloom?
The optimal strategy is a greedy approach that sorts seeds by decreasing growTime. Seeds with the longest growth duration are planted first so their long growth phase starts as early as possible. After sorting, iterate once while accumulating planting days and computing each seed’s bloom day. The final answer is the maximum bloom day across all seeds.
Is Earliest Possible Day of Full Bloom asked at Google/Amazon/Meta?
Greedy scheduling and task ordering problems like this frequently appear in interviews at companies such as Google, Amazon, and Meta. The problem tests whether you can reason about sequential work combined with parallel completion times and identify the correct greedy ordering.
What data structure is used in Earliest Possible Day of Full Bloom?
The solution mainly uses arrays and sorting. Seeds are often paired as (plantTime, growTime) and sorted by growTime in descending order. A simple running sum variable tracks cumulative planting time while iterating through the sorted list.
What is the time complexity of Earliest Possible Day of Full Bloom?
The optimal solution runs in O(n log n) time because the seeds must be sorted by growTime. After sorting, a single linear pass computes cumulative planting time and bloom days. Space complexity is typically O(n) if pairs or indices are stored during sorting.

Ready to solve this problem?

Practice Earliest Possible Day of Full Bloom with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Number of Days to Make m Bouquets