Earliest Possible Day of Full Bloom - Practice Coding Problems

Earliest Possible Day of Full Bloom - 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.

Input & Output

Example 1 — Basic Case

$ Input: plantTime = [1,4,3], growTime = [2,3,1]

› Output: 9

💡 Note: Optimal order is to plant seed 1 (grow time 3), then seed 0 (grow time 2), then seed 2 (grow time 1). Plant seed 1 on days 0-3 (completes day 4), blooms day 7. Plant seed 0 on day 4 (completes day 5), blooms day 7. Plant seed 2 on days 5-7 (completes day 8), blooms day 9. All seeds bloom by day 9.

Example 2 — Equal Plant Times

$ Input: plantTime = [1,2,3,2], growTime = [2,1,2,1]

› Output: 9

💡 Note: Sort by grow time descending: seeds 0,2 (grow=2), then seeds 1,3 (grow=1). Plant in order [0,2,1,3]. Seed 0: plant days 0, blooms day 1+2=3. Seed 2: plant days 1-3, blooms day 4+2=6. Seed 1: plant days 4-5, blooms day 6+1=7. Seed 3: plant days 6-7, blooms day 8+1=9.

Example 3 — Single Seed

$ Input: plantTime = [1], growTime = [1]

› Output: 2

💡 Note: Only one seed: plant it on day 0, completes day 1, blooms on day 1+1=2.

Constraints

n == plantTime.length == growTime.length
1 ≤ n ≤ 10⁵
1 ≤ plantTime[i], growTime[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Two arrays: plant times and grow times for each seed

Strategy

Sort by grow time (longest first) to optimize scheduling

Output

Earliest day when all seeds have bloomed

Key Takeaway

🎯 Key Insight: Plant seeds with longest grow times first to minimize total completion time

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Meta 6

The key insight is that we should plant seeds with longer grow times first to minimize the overall completion time. The optimal approach sorts seeds by grow time in descending order and plants them sequentially. Time: O(n log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Try All Permutations	O(n! × n)	O(n)	Generate all possible planting orders and find the minimum completion day
Greedy: Sort by Grow Time	O(n log n)	O(n)	Sort seeds by grow time in descending order and plant in that sequence

Try All Permutations — Algorithm Steps

Generate all possible planting orders
For each order, calculate bloom completion day
Track minimum completion day across all orders

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Permutations

Create all possible planting orders

Calculate Each Order

For each order, compute when all flowers bloom

Find Minimum

Return the earliest completion day

Code -

solution.c — C

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

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int minResult = INT_MAX;

void permute(int* plantTime, int* growTime, int* indices, int start, int n) {
    if (start == n) {
        int currentPlantDay = 0;
        int maxBloomDay = 0;
        
        for (int j = 0; j < n; j++) {
            int i = indices[j];
            int plantCompleteDay = currentPlantDay + plantTime[i];
            currentPlantDay = plantCompleteDay;
            int bloomDay = plantCompleteDay + growTime[i];
            if (bloomDay > maxBloomDay) maxBloomDay = bloomDay;
        }
        
        if (maxBloomDay < minResult) minResult = maxBloomDay;
        return;
    }
    
    for (int i = start; i < n; i++) {
        swap(&indices[start], &indices[i]);
        permute(plantTime, growTime, indices, start + 1, n);
        swap(&indices[start], &indices[i]);
    }
}

int solution(int* plantTime, int* growTime, int n) {
    minResult = INT_MAX;
    int* indices = malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) indices[i] = i;
    
    permute(plantTime, growTime, indices, 0, n);
    
    free(indices);
    return minResult;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse first array
    int plantTime[20], growTime[20];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL && n < 20) {
        plantTime[n++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    fgets(line, sizeof(line), stdin);
    int m = 0;
    token = strtok(line, "[,]");
    while (token != NULL && m < 20) {
        growTime[m++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    printf("%d\n", solution(plantTime, growTime, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n! × n)

n! permutations, each taking O(n) time to calculate completion

⚠ Quadratic Growth

Space Complexity

O(n)

Storage for current permutation and tracking variables

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

845 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Try All Permutations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler