2136. Earliest Possible Day of Full Bloom Solution

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

The problem

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 i^th 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 i^th 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 0^th seed. The seed grows for 2 full days and blooms on day 3.
On days 1, 2, 3, and 4, plant the 1^st seed. The seed grows for 3 full days and blooms on day 8.
On days 5, 6, and 7, plant the 2^nd 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 0^th seed. The seed grows for 2 full days and blooms on day 4.
On days 0 and 3, plant the 1^st seed. The seed grows for 1 full day and blooms on day 5.
On days 2, 4, and 5, plant the 2^nd seed. The seed grows for 2 full days and blooms on day 8.
On days 6 and 7, plant the 3^rd 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 0^th 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 <= 10⁵
1 <= plantTime[i], growTime[i] <= 10⁴

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.

Python

def earliestFullBloom(plantTime, growTime):
    seeds = sorted(zip(plantTime, growTime), key=lambda x: x[0])
    current_day = 0
    last_bloom_day = 0

    for pt, gt in seeds:
        current_day += pt
        last_bloom_day = max(last_bloom_day, current_day + gt)

    return last_bloom_day


plantTime = [1, 4, 3]
growTime = [2, 3, 1]
result = earliestFullBloom(plantTime, growTime)
print(f"Earliest Full Bloom Day: {result}")

Java

import java.util.*;

class Seed {
    int plantTime;
    int growTime;

    Seed(int plantTime, int growTime) {
        this.plantTime = plantTime;
        this.growTime = growTime;
    }
}

public class Main {
    public static int earliestFullBloom(int[] plantTime, int[] growTime) {
        int n = plantTime.length;
        Seed[] seeds = new Seed[n];

        for (int i = 0; i < n; ++i) {
            seeds[i] = new Seed(plantTime[i], growTime[i]);
        }

        Arrays.sort(seeds, (a, b) -> a.plantTime - b.plantTime);

        int currentDay = 0;
        int lastBloomDay = 0;

        for (Seed seed : seeds) {
            currentDay += seed.plantTime;
            lastBloomDay = Math.max(lastBloomDay, currentDay + seed.growTime);
        }

        return lastBloomDay;
    }

    public static void main(String[] args) {
        int[] plantTime = {1, 4, 3};
        int[] growTime = {2, 3, 1};
        System.out.println("Earliest Full Bloom Day: " + earliestFullBloom(plantTime, growTime));
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Seed {
    int plantTime;
    int growTime;
};

bool compare(const Seed& a, const Seed& b) {
    return a.plantTime < b.plantTime;
}

int earliestFullBloom(vector<int>& plantTime, vector<int>& growTime) {
    int n = plantTime.size();
    vector<Seed> seeds(n);
    for (int i = 0; i < n; ++i) {
        seeds[i] = {plantTime[i], growTime[i]};
    }
    sort(seeds.begin(), seeds.end(), compare);

    int currentDay = 0;
    int lastBloomDay = 0;
    for (const auto& seed : seeds) {
        currentDay += seed.plantTime;
        lastBloomDay = max(lastBloomDay, currentDay + seed.growTime);
    }
    return lastBloomDay;
}

int main() {
    vector<int> plantTime = {1, 4, 3};
    vector<int> growTime = {2, 3, 1};
    cout << "Earliest Full Bloom Day: " << earliestFullBloom(plantTime, growTime) << endl;
    return 0;
}

JavaScript

function earliestFullBloom(plantTime, growTime) {
    const seeds = plantTime.map((pt, idx) => ({
        plantTime: pt,
        growTime: growTime[idx]
    }));

    seeds.sort((a, b) => a.plantTime - b.plantTime);

    let currentDay = 0;
    let lastBloomDay = 0;

    for (let i = 0; i < seeds.length; i++) {
        currentDay += seeds[i].plantTime;
        lastBloomDay = Math.max(lastBloomDay, currentDay + seeds[i].growTime);
    }

    return lastBloomDay;
}

const plantTime = [1, 4, 3];
const growTime = [2, 3, 1];
console.log("Earliest Full Bloom Day:", earliestFullBloom(plantTime, growTime));

#include <stdio.h>
#include <stdlib.h>

struct Seed {
    int plantTime;
    int growTime;
};

int compare(const void *a, const void *b) {
    struct Seed *seedA = (struct Seed *)a;
    struct Seed *seedB = (struct Seed *)b;
    return seedA->plantTime - seedB->plantTime;
}

int earliestFullBloom(int* plantTime, int plantTimeSize, int* growTime, int growTimeSize) {
    struct Seed seeds[plantTimeSize];
    for (int i = 0; i < plantTimeSize; i++) {
        seeds[i].plantTime = plantTime[i];
        seeds[i].growTime = growTime[i];
    }
    
    qsort(seeds, plantTimeSize, sizeof(struct Seed), compare);
    
    int currentDay = 0;
    int lastBloomDay = 0;
    for (int i = 0; i < plantTimeSize; i++) {
        currentDay += seeds[i].plantTime;
        int bloomDay = currentDay + seeds[i].growTime;
        if (bloomDay > lastBloomDay) {
            lastBloomDay = bloomDay;
        }
    }
    return lastBloomDay;
}

int main() {
    int plantTime[] = {1, 4, 3};
    int growTime[] = {2, 3, 1};
    int result = earliestFullBloom(plantTime, 3, growTime, 3);
    printf("Earliest Full Bloom Day: %d\n", result);
    return 0;
}

using System;
using System.Linq;

class Seed {
    public int PlantTime { get; set; }
    public int GrowTime { get; set; }
}

class Program {
    public static int EarliestFullBloom(int[] plantTime, int[] growTime) {
        Seed[] seeds = new Seed[plantTime.Length];

        for (int i = 0; i < plantTime.Length; i++) {
            seeds[i] = new Seed { PlantTime = plantTime[i], GrowTime = growTime[i] };
        }

        Array.Sort(seeds, (a, b) => a.PlantTime.CompareTo(b.PlantTime));

        int currentDay = 0;
        int lastBloomDay = 0;

        foreach (var seed in seeds) {
            currentDay += seed.PlantTime;
            lastBloomDay = Math.Max(lastBloomDay, currentDay + seed.GrowTime);
        }

        return lastBloomDay;
    }

    static void Main() {
        int[] plantTime = { 1, 4, 3 };
        int[] growTime = { 2, 3, 1 };
        Console.WriteLine("Earliest Full Bloom Day: " + EarliestFullBloom(plantTime, growTime));
    }
}

The Python solution utilizes zip and sorted to manage the sorting and ordering of planting and growing operations, keeping track of cumulative days for bloom calculations.

Complexity

Time Complexity: O(n log n), primarily from sorting operations. Space Complexity: O(n), storing the seed tuples.

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.

Python

def earliestFullBloom(plantTime, growTime):
    seeds = sorted(zip(plantTime, growTime), key=lambda x: -x[1])
    current_day = 0
    last_bloom_day = 0

    for pt, gt in seeds:
        current_day += pt
        last_bloom_day = max(last_bloom_day, current_day + gt)

    return last_bloom_day


plantTime = [1, 4, 3]
growTime = [2, 3, 1]
result = earliestFullBloom(plantTime, growTime)
print(f"Earliest Full Bloom Day: {result}")

Java

import java.util.*;

class Seed {
    int plantTime;
    int growTime;

    Seed(int plantTime, int growTime) {
        this.plantTime = plantTime;
        this.growTime = growTime;
    }
}

public class Main {
    public static int earliestFullBloom(int[] plantTime, int[] growTime) {
        int n = plantTime.length;
        Seed[] seeds = new Seed[n];

        for (int i = 0; i < n; ++i) {
            seeds[i] = new Seed(plantTime[i], growTime[i]);
        }

        Arrays.sort(seeds, (a, b) -> b.growTime - a.growTime);

        int totalPlantDays = 0;
        int maxBloomDay = 0;

        for (Seed seed : seeds) {
            totalPlantDays += seed.plantTime;
            maxBloomDay = Math.max(maxBloomDay, totalPlantDays + seed.growTime);
        }

        return maxBloomDay;
    }

    public static void main(String[] args) {
        int[] plantTime = {1, 4, 3};
        int[] growTime = {2, 3, 1};
        System.out.println("Earliest Full Bloom Day: " + earliestFullBloom(plantTime, growTime));
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Seed {
    int plantTime;
    int growTime;
};

bool compare(const Seed& a, const Seed& b) {
    return a.growTime > b.growTime;
}

int earliestFullBloom(vector<int>& plantTime, vector<int>& growTime) {
    int n = plantTime.size();
    vector<Seed> seeds(n);
    for (int i = 0; i < n; ++i) {
        seeds[i] = {plantTime[i], growTime[i]};
    }
    sort(seeds.begin(), seeds.end(), compare);

    int totalPlantDays = 0;
    int maxBloomDay = 0;

    for (const auto& seed : seeds) {
        totalPlantDays += seed.plantTime;
        maxBloomDay = max(maxBloomDay, totalPlantDays + seed.growTime);
    }
    
    return maxBloomDay;
}

int main() {
    vector<int> plantTime = {1, 4, 3};
    vector<int> growTime = {2, 3, 1};
    cout << "Earliest Full Bloom Day: " << earliestFullBloom(plantTime, growTime) << endl;
    return 0;
}

JavaScript

function earliestFullBloom(plantTime, growTime) {
    const seeds = plantTime.map((pt, idx) => ({
        plantTime: pt,
        growTime: growTime[idx]
    }));

    seeds.sort((a, b) => b.growTime - a.growTime);

    let totalPlantDays = 0;
    let maxBloomDay = 0;

    for (let i = 0; i < seeds.length; i++) {
        totalPlantDays += seeds[i].plantTime;
        maxBloomDay = Math.max(maxBloomDay, totalPlantDays + seeds[i].growTime);
    }

    return maxBloomDay;
}

const plantTime = [1, 4, 3];
const growTime = [2, 3, 1];
console.log("Earliest Full Bloom Day:", earliestFullBloom(plantTime, growTime));

#include <stdio.h>
#include <stdlib.h>

struct Seed {
    int plantTime;
    int growTime;
};

int compare(const void *a, const void *b) {
    struct Seed *seedA = (struct Seed *)a;
    struct Seed *seedB = (struct Seed *)b;
    return seedB->growTime - seedA->growTime;
}

int earliestFullBloom(int* plantTime, int plantTimeSize, int* growTime, int growTimeSize) {
    struct Seed seeds[plantTimeSize];
    for (int i = 0; i < plantTimeSize; i++) {
        seeds[i].plantTime = plantTime[i];
        seeds[i].growTime = growTime[i];
    }
    
    qsort(seeds, plantTimeSize, sizeof(struct Seed), compare);
    
    int totalPlantDays = 0;
    int maxBloomDay = 0;
    for (int i = 0; i < plantTimeSize; i++) {
        totalPlantDays += seeds[i].plantTime;
        int bloomDay = totalPlantDays + seeds[i].growTime;
        if (bloomDay > maxBloomDay) {
            maxBloomDay = bloomDay;
        }
    }
    return maxBloomDay;
}

int main() {
    int plantTime[] = {1, 4, 3};
    int growTime[] = {2, 3, 1};
    int result = earliestFullBloom(plantTime, 3, growTime, 3);
    printf("Earliest Full Bloom Day: %d\n", result);
    return 0;
}

using System;
using System.Linq;

class Seed {
    public int PlantTime { get; set; }
    public int GrowTime { get; set; }
}

class Program {
    public static int EarliestFullBloom(int[] plantTime, int[] growTime) {
        Seed[] seeds = new Seed[plantTime.Length];

        for (int i = 0; i < plantTime.Length; i++) {
            seeds[i] = new Seed { PlantTime = plantTime[i], GrowTime = growTime[i] };
        }

        Array.Sort(seeds, (a, b) => b.GrowTime.CompareTo(a.GrowTime));

        int totalPlantDays = 0;
        int maxBloomDay = 0;

        foreach (var seed in seeds) {
            totalPlantDays += seed.PlantTime;
            maxBloomDay = Math.Max(maxBloomDay, totalPlantDays + seed.GrowTime);
        }

        return maxBloomDay;
    }

    static void Main() {
        int[] plantTime = { 1, 4, 3 };
        int[] growTime = { 2, 3, 1 };
        Console.WriteLine("Earliest Full Bloom Day: " + EarliestFullBloom(plantTime, growTime));
    }
}

The Python solution creates a zip object and sorts it on grow times. It represents a computationally simple simulation of the day-to-day planting strategy.

Complexity

Time Complexity: O(n log n), stemming from the sorting operation. Space Complexity: O(n), resulting from storing tuples of 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.

TypeScript

function earliestFullBloom(plantTime: number[], growTime: number[]): number {
    const n = plantTime.length;
    const idx: number[] = Array.from({ length: n }, (_, i) => i);
    idx.sort((i, j) => growTime[j] - growTime[i]);
    let [ans, t] = [0, 0];
    for (const i of idx) {
        t += plantTime[i];
        ans = Math.max(ans, t + growTime[i]);
    }
    return ans;
}

func earliestFullBloom(plantTime []int, growTime []int) (ans int) {
	n := len(plantTime)
	idx := make([]int, n)
	for i := range idx {
		idx[i] = i
	}
	sort.Slice(idx, func(i, j int) bool { return growTime[idx[j]] < growTime[idx[i]] })
	t := 0
	for _, i := range idx {
		t += plantTime[i]
		ans = max(ans, t+growTime[i])
	}
	return
}

Rust

impl Solution {
    pub fn earliest_full_bloom(plant_time: Vec<i32>, grow_time: Vec<i32>) -> i32 {
        let mut idx: Vec<usize> = (0..plant_time.len()).collect();
        idx.sort_by_key(|&i| -&grow_time[i]);
        let mut ans = 0;
        let mut t = 0;
        for &i in &idx {
            t += plant_time[i];
            ans = ans.max(t + grow_time[i]);
        }
        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Shorter Plant Time Priority	Time Complexity: O(n log n), primarily from sorting operations. Space Complexity: O(n), storing the seed tuples.
Long Grow Time Priority	Time Complexity: O(n log n), stemming from the sorting operation. Space Complexity: O(n), resulting from storing tuples of seed data.
Greedy + Sorting	–

Complexity analysis

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

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.

Earliest Possible Day of Full Bloom solution and explanation

The problem

Approach overview

Approach 1: Shorter Plant Time Priority

Approach 2: Long Grow Time Priority

Approach 3: Greedy + Sorting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Earliest Possible Day of Full Bloom solution and explanation

The problem

Approach overview

Approach 1: Shorter Plant Time Priority

Approach 2: Long Grow Time Priority

Approach 3: Greedy + Sorting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems