We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Earliest Possible Day of Full Bloom

Number: 2257

Difficulty: Hard

Paid? No

Companies: Visa

Problem Description

We are given n flower seeds with two arrays: plantTime and growTime. Planting each seed takes plantTime[i] full days, and after planting, each seed requires growTime[i] full days to bloom. Only one seed can be planted per day (though planting days for a seed need not be consecutive). The task is to determine the earliest day on which all seeds have bloomed when you can plant them in any order.

Key Insights

  • The order in which you plant the seeds influences the overall blooming day.
  • Seeds with longer growTime benefit from being planted earlier, as their growth can occur concurrently with the planting of other seeds.
  • Sorting the seeds by descending growTime ensures that seeds taking longest to grow start their growth phase as early as possible.
  • The final result is the maximum among (cumulative planting days + respective growTime) across all seeds.

Space and Time Complexity

Time Complexity: O(n log n) due to the sorting step, followed by an O(n) iteration. Space Complexity: O(n) for storing the paired seed information.

Solution

The approach is to first pair each seed's plantTime and growTime. Sort these pairs in descending order based on growTime so that seeds requiring more time to grow are planted earlier. Then, simulate the planting process: accumulate the planting time sequentially for each seed and compute the potential bloom day as the sum of the current cumulative planting time and the seed’s growTime. The earliest day when all seeds have bloomed is the maximum of these computed bloom days.

Code Solutions

# Function to calculate the earliest day when all seeds have bloomed
def earliestFullBloom(plantTime, growTime):
    # Pair each seed's plant time with its grow time
    seeds = list(zip(plantTime, growTime))
    # Sort seeds in descending order of grow time
    seeds.sort(key=lambda x: -x[1])
    current_day = 0  # Cumulative days spent on planting so far
    bloom_day = 0    # Maximum bloom day encountered
    # Process each seed in the sorted order
    for plant, grow in seeds:
        current_day += plant             # Increment current day by planting time for current seed
        bloom_day = max(bloom_day, current_day + grow)  # Update the overall bloom day
    return bloom_day

# Example usage:
print(earliestFullBloom([1, 4, 3], [2, 3, 1]))  # Expected output: 9
← Back to All Questions