< Back





2136. Earliest Possible Day of Full Bloom

We're given two arrays, plantTime and growTime, that represent how long it takes us to plant a flower
and how long it takes us to grow a flower. We're asked to find the earliest time possible where all
flowers are blooming - this will always occur one day after the plant's grow time
(plantTime + growTime + 1).

Using our intuition, we can't really optimize for plantTime. No matter what, time is restricted by
sum(plantTime[n]) for all plants. We optimize for growTime because the final bloom of all the flowers
is restricted by the maximum growTime. We don't want to be planting flowers that have a shorter
growTime while a plant with a longer growTime could already be growing.

Thus, we sort by highest growTime and iterate through the plants. We keep track of our answer,
the earliest day we get a full bloom, and the current time, t. We iterate through the sorted list of
germination periods for the flowers, and add the plantTime of the current plant to our time
elapsed, t. We take the maximum of max(answer, t + growTime) because we want to find the earliest
time where all flowers are blooming.

The solution is as follows:


  class Solution:
      def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:
          germ = sorted([(start, end) for start, end in zip(plantTime, growTime)], key=lambda x: -x[1])
          ans = t = 0

          for start, end in germ:
              t += start
              ans = max(ans, t + end)

          return ans


_ Time Complexity:

  O(n log(n)) - We have to sort the input.

_ Space Complexity:

  O(n) - Python sorting takes O(n) space.