LeetCode 2136 - Earliest Possible Day of Full Bloom

LeetCode Problem 2136

Difficulty: 🔴 Hard
Topics: Array, Greedy, Sorting

Solution

Problem Understanding

The problem presents a scenario where we have n flower seeds, each of which requires two phases to bloom: a planting phase and a growth phase. Each seed i takes plantTime[i] full days to plant, which can be spread across non-consecutive days. After planting, the seed requires growTime[i] full days to grow, and only after this period does the flower bloom. The goal is to determine the earliest possible day when all flowers have bloomed.

The input consists of two equal-length arrays: plantTime and growTime. The output is a single integer representing the earliest day on which every flower has fully bloomed. The constraints indicate that n can be up to 100,000 and individual times up to 10,000, so naive approaches that explore all permutations of planting order will be too slow. Importantly, the problem guarantees positive integers for both planting and growth times, so we do not need to handle zero or negative values.

Key edge cases to consider include when there is only one seed, when all growTime values are identical, or when planting times are larger than growth times or vice versa. These edge cases could challenge naive scheduling strategies.

Approaches

Brute Force Approach

A brute force approach would attempt to try every possible permutation of seed planting order, compute the bloom day for each sequence, and return the minimum bloom day among all permutations. For each permutation, the bloom day for a seed is the cumulative planting time up to that seed plus its growth time. While correct, this approach is computationally infeasible for large n because the number of permutations is n!, which grows factorially.

Optimal Approach

The key insight is that the order of planting affects when the last seed blooms. To minimize the overall bloom day, we should prioritize planting seeds that take longer to grow earlier. The reasoning is that long-growing seeds act as bottlenecks; planting them early allows their growth to proceed in parallel with the planting of other seeds. This is essentially a greedy strategy: sort the seeds by descending growTime and plant them in that order. Then, track the cumulative planting days and compute the bloom day for each seed as current_plant_day + growTime[i]. The maximum of these bloom days gives the earliest day all seeds are blooming.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n!)	O(n)	Generates all permutations and computes bloom day
Optimal	O(n log n)	O(n)	Sort by growTime descending and greedily compute bloom days

Algorithm Walkthrough

1. Pair each seed's plantTime and growTime together to keep track of both values for sorting.

2. Sort the seeds by growTime in descending order, ensuring seeds with longer growth periods are planted first.

3. Initialize two variables: current_day to track cumulative planting days and earliest_full_bloom to track the latest bloom day.

4. Iterate through the sorted seeds:

5. Increment current_day by the seed's plantTime, representing the days spent planting up to and including this seed.

6. Compute the bloom day of the seed as current_day + growTime.

7. Update earliest_full_bloom as the maximum of its current value and the bloom day of this seed.

8. After processing all seeds, earliest_full_bloom contains the earliest day when all seeds have bloomed.

Why it works: By planting seeds with longer growth times first, we allow their growth to overlap with the planting of shorter-growing seeds, minimizing the maximum bloom day. This greedy strategy guarantees the earliest possible day without needing to consider all permutations.

Python Solution

from typing import List

class Solution:
    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:
        seeds = list(zip(plantTime, growTime))
        seeds.sort(key=lambda x: -x[1])  # Sort by growTime descending

        current_day = 0
        earliest_full_bloom = 0

        for plant, grow in seeds:
            current_day += plant
            earliest_full_bloom = max(earliest_full_bloom, current_day + grow)

        return earliest_full_bloom

The Python implementation pairs each seed's planting and growth times, sorts the seeds by descending growth time, then iterates to accumulate planting days while tracking the latest bloom day. This corresponds exactly to the algorithm walkthrough.

Go Solution

import "sort"

func earliestFullBloom(plantTime []int, growTime []int) int {
    n := len(plantTime)
    seeds := make([][2]int, n)
    for i := 0; i < n; i++ {
        seeds[i] = [2]int{plantTime[i], growTime[i]}
    }

    sort.Slice(seeds, func(i, j int) bool {
        return seeds[i][1] > seeds[j][1] // Descending growTime
    })

    currentDay := 0
    earliestFullBloom := 0

    for _, seed := range seeds {
        currentDay += seed[0]
        if currentDay+seed[1] > earliestFullBloom {
            earliestFullBloom = currentDay + seed[1]
        }
    }

    return earliestFullBloom
}

The Go implementation is similar to Python, with slices used to store the seed tuples. Sorting is handled using sort.Slice. Integer addition and comparisons ensure correct tracking of cumulative planting days and maximum bloom day.

Worked Examples

Example 1

plantTime = [1,4,3], growTime = [2,3,1]
Sorted by growTime descending: [(4,3), (1,2), (3,1)]

Iteration:

Seed	current_day	bloom_day	earliest_full_bloom
(4,3)	4	7	7
(1,2)	5	7	7
(3,1)	8	9	9

Output: 9

Example 2

plantTime = [1,2,3,2], growTime = [2,1,2,1]
Sorted: [(1,2), (3,2), (2,1), (2,1)]

Iteration:

Seed	current_day	bloom_day	earliest_full_bloom
(1,2)	1	3	3
(3,2)	4	6	6
(2,1)	6	7	7
(2,1)	8	9	9

Output: 9

Example 3

plantTime = [1], growTime = [1]
Sorted: [(1,1)]
current_day = 1
bloom_day = 2
earliest_full_bloom = 2

Output: 2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting n seeds dominates; iteration is O(n)
Space	O(n)	Storage of seed tuples for sorting

The algorithm is efficient because it avoids factorial complexity and only requires sorting and a single pass.

Test Cases

# Provided examples
assert Solution().earliestFullBloom([1,4,3], [2,3,1]) == 9  # Example 1
assert Solution().earliestFullBloom([1,2,3,2], [2,1,2,1]) == 9  # Example 2
assert Solution().earliestFullBloom([1], [1]) == 2  # Example 3

# Edge cases
assert Solution().earliestFullBloom([1,1,1], [1,1,1]) == 4  # All same
assert Solution().earliestFullBloom([5,1,1], [1,10,1]) == 17  # Large growTime first
assert Solution().earliestFullBloom([1]*100000, [10000]*100000) == 10000 + 100000  # Stress test

Test	Why
[1,4,3], [2,3,1]	Validates general scenario with different planting and growth times
[1,2,3,2], [2,1,2,1]	Checks interleaving planting and growth
[1], [1]	Single element edge case
[1,1,1], [1,1,1]	All equal times
[5,1,1], [1,10,1]	Ensures long-growing seed early in optimal order
Large stress test	Performance and scale validation

Edge Cases

One important edge case is when there is only one seed. The algorithm correctly handles it because sorting a single element does not change order, and the bloom day is simply plantTime[0] + growTime[0].

Another edge case is when multiple seeds have identical growth times. The sort maintains a deterministic order, and the cumulative planting days are correctly tracked, ensuring no miscalculations in bloom day.

A third edge case is when one seed