# Earliest Possible Day of Full Bloom
**Difficulty:** HARD
[External](https://leetcode.com/problems/earliest-possible-day-of-full-bloom)
Canonical: https://scaleengineer.com/dsa/problems/earliest-possible-day-of-full-bloom
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Visa](https://scaleengineer.com/companies/visa)
---
## 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 `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:**

![](https://assets.glich.co/dsa/earliest-possible-day-of-full-bloom/image0.png) 

**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:**

![](https://assets.glich.co/dsa/earliest-possible-day-of-full-bloom/image1.png) 

**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`

# Approaches
## Brute Force with Permutations
This approach exhaustively checks every possible order of planting the seeds. By generating all permutations of the seeds, we can calculate the total time required for all flowers to bloom for each specific order. The minimum time found among all permutations will be the correct answer. While correct, this method is computationally very expensive.
**Time:** O(n! * n) - There are `n!` possible permutations of the seeds. For each permutation, we iterate through all `n` seeds to calculate the total bloom time. This results in a factorial time complexity, which is not feasible for the given constraints where `n` can be up to 10^5. · **Space:** O(n) - The space is primarily used for the recursion stack, which can go up to `n` levels deep. We also use an array of size `n` to store the current permutation.
**Pros:** Conceptually simple and straightforward to understand.; Guaranteed to find the optimal solution because it explores the entire search space.
**Cons:** Extremely inefficient and slow.; Guaranteed to receive a 'Time Limit Exceeded' (TLE) error on any platform for the given constraints.; Only feasible for very small inputs (e.g., n <= 10).
### Explanation
The fundamental idea is to solve the problem by brute force. Since we can plant seeds in any order, we can try every single sequence. There are `n!` (n factorial) possible sequences to plant `n` seeds. We can generate each of these sequences (permutations) using a standard algorithm, like Heap's algorithm or a recursive backtracking approach.

For each generated permutation, we simulate the planting process from day 0. We maintain a running total of the time spent planting, let's call it `currentPlantTime`. As we process each seed in the sequence, we add its `plantTime` to `currentPlantTime`. The day this seed will bloom is `currentPlantTime + growTime` for that seed. We calculate this bloom day for every seed in the sequence and find the maximum among them. This maximum value is the time it takes for all flowers to bloom for that specific planting order.

Finally, we compare this maximum value with a global minimum we're tracking across all permutations and update it if the current sequence is better. After checking all `n!` permutations, the global minimum will hold the earliest possible day of full bloom.

```java
class Solution {
    int minBloomDay = Integer.MAX_VALUE;

    public int earliestFullBloom(int[] plantTime, int[] growTime) {
        int n = plantTime.length;
        java.util.ArrayList<Integer> indices = new java.util.ArrayList<>();
        for (int i = 0; i < n; i++) {
            indices.add(i);
        }
        generatePermutations(indices, 0, plantTime, growTime);
        return minBloomDay;
    }

    private void generatePermutations(java.util.ArrayList<Integer> indices, int start, int[] plantTime, int[] growTime) {
        if (start >= indices.size()) {
            calculateBloomTime(indices, plantTime, growTime);
            return;
        }
        for (int i = start; i < indices.size(); i++) {
            java.util.Collections.swap(indices, start, i);
            generatePermutations(indices, start + 1, plantTime, growTime);
            java.util.Collections.swap(indices, start, i); // backtrack
        }
    }

    private void calculateBloomTime(java.util.ArrayList<Integer> order, int[] plantTime, int[] growTime) {
        int currentPlantTime = 0;
        int maxBloomTime = 0;
        for (int index : order) {
            currentPlantTime += plantTime[index];
            int bloomTime = currentPlantTime + growTime[index];
            if (bloomTime > maxBloomTime) {
                maxBloomTime = bloomTime;
            }
        }
        if (maxBloomTime < minBloomDay) {
            minBloomDay = maxBloomTime;
        }
    }
}
```
### Algorithm
- Create a list of seed indices from `0` to `n-1`.
- Implement a recursive helper function `generatePermutations(indices, start)` to explore all possible planting orders.
- **Base Case:** When a full permutation is generated (i.e., `start` reaches the end of the list), calculate the total bloom time for this specific order.
- To calculate bloom time for a permutation:
    - Initialize `currentPlantTime = 0` and `maxBloomTime = 0`.
    - Iterate through the seed indices in the permutation's order.
    - For each seed, add its `plantTime` to `currentPlantTime`.
    - The bloom day for this seed is `currentPlantTime + growTime`.
    - Update `maxBloomTime` with the maximum bloom day seen so far.
- Keep a global variable to track the minimum `maxBloomTime` found across all permutations.
- **Recursive Step:** In the `generatePermutations` function, iterate from `start` to the end of the list, swapping the element at `start` with the current element, making a recursive call, and then swapping back to backtrack.

## Greedy Approach by Sorting on Grow Time
A much more efficient and optimal solution can be achieved using a greedy strategy. The core intuition is that seeds with longer growth times are the most likely to be the bottleneck for the final bloom day. Therefore, it's beneficial to plant them as early as possible. This allows their long growth period to overlap with the planting time of subsequent seeds. By prioritizing seeds with the longest `growTime`, we can minimize the overall time until all seeds have bloomed.
**Time:** O(n log n) - The main bottleneck of this approach is sorting the `n` seeds. This takes `O(n log n)` time. The subsequent loop to calculate the maximum bloom day runs in `O(n)` time. Thus, the total time complexity is `O(n log n)`. · **Space:** O(n) - We use an auxiliary array of size `n` to store the `Seed` objects (or pairs of times) to facilitate sorting. The space used by the sorting algorithm itself also contributes, which is typically O(log n) or O(n) depending on the implementation.
**Pros:** Highly efficient and provides the optimal solution.; The time complexity is dominated by sorting, making it fast enough for the given constraints.; The implementation is straightforward once the greedy strategy is established.
**Cons:** The greedy choice is not immediately obvious and requires a proof (like an exchange argument) to be certain of its correctness.; Requires extra space to store the combined seed data for sorting.
### Explanation
The problem can be solved optimally by determining the best order to plant the seeds. An exchange argument can prove the optimal strategy: for any two adjacent seeds in a planting sequence, it is always better or equal to plant the one with the larger `growTime` first. This is because planting a long-`growTime` seed earlier gives it a head start. Its growth can happen in parallel with the planting of other seeds, effectively hiding the long growth duration behind other necessary work.

This insight leads to a simple greedy algorithm:
1.  Combine the `plantTime` and `growTime` for each seed into a single entity.
2.  Sort these seeds in descending order of their `growTime`.
3.  Iterate through the sorted list of seeds, simulating the planting process. We maintain a `currentPlantTime` which represents the total days spent on planting so far. For each seed, we add its `plantTime` to `currentPlantTime`. The bloom time for this seed is its planting completion time (`currentPlantTime`) plus its `growTime`. We keep track of the maximum bloom time encountered.

This maximum bloom time after considering all seeds in the sorted order is the earliest possible day all seeds can be in bloom.

```java
class Solution {
    class Seed {
        int plantTime;
        int growTime;

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

    public 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]);
        }

        // Sort seeds based on growTime in descending order
        java.util.Arrays.sort(seeds, (a, b) -> b.growTime - a.growTime);

        int maxBloomDay = 0;
        int currentPlantTime = 0;
        for (Seed seed : seeds) {
            currentPlantTime += seed.plantTime;
            int bloomDay = currentPlantTime + seed.growTime;
            if (bloomDay > maxBloomDay) {
                maxBloomDay = bloomDay;
            }
        }

        return maxBloomDay;
    }
}
```
### Algorithm
- Create a structure or class, say `Seed`, to store pairs of `plantTime` and `growTime`.
- Populate an array of `Seed` objects with the given `plantTime` and `growTime` arrays.
- Sort this array of `Seed` objects in descending order based on their `growTime`.
- Initialize two variables: `maxBloomDay = 0` and `currentPlantTime = 0`.
- Iterate through the sorted seeds:
    - For each seed, add its `plantTime` to `currentPlantTime`.
    - Calculate the bloom day for the current seed: `bloomDay = currentPlantTime + seed.growTime`.
    - Update the overall maximum bloom day: `maxBloomDay = max(maxBloomDay, bloomDay)`.
- After iterating through all the seeds, `maxBloomDay` will hold the earliest possible day of full bloom. Return this value.

# Solutions
### Java

```java
class Solution { public int earliestFullBloom ( int [] plantTime , int [] growTime ) { int n = plantTime . length ; Integer [] idx = new Integer [ n ]; for ( int i = 0 ; i < n ; i ++) { idx [ i ] = i ; } Arrays . sort ( idx , ( i , j ) -> growTime [ j ] - growTime [ i ]); int ans = 0 , t = 0 ; for ( int i : idx ) { t += plantTime [ i ]; ans = Math . max ( ans , t + growTime [ i ]); } return ans ; } }
```

### CPP

```cpp
class Solution { public: int earliestFullBloom ( vector < int >& plantTime , vector < int >& growTime ) { int n = plantTime . size (); vector < int > idx ( n ); iota ( idx . begin (), idx . end (), 0 ); sort ( idx . begin (), idx . end (), [ & ]( int i , int j ) { return growTime [ j ] < growTime [ i ]; }); int ans = 0 , t = 0 ; for ( int i : idx ) { t += plantTime [ i ]; ans = max ( ans , t + growTime [ i ]); } return ans ; } };
```

### Python

```python
class Solution : def earliestFullBloom ( self , plantTime : List [ int ], growTime : List [ int ]) -> int : ans = t = 0 for pt , gt in sorted ( zip ( plantTime , growTime ), key = lambda x : - x [ 1 ]): t += pt ans = max ( ans , t + gt ) return ans
```