Let's now discuss the space and time complexity of the approach that we have discussed in the previous
video.
So these are the two steps that we had.
We first had to sort the envelopes and then we applied lis on the second element.
Okay.
Now sorting the envelopes will take up work of the order of n log n.
And when it comes to space it will take up space either of the order of log n if you are using quicksort
or even constant space if you are using something like heapsort.
Okay.
And the second step, which is to apply lis on the second element, can be done in multiple ways, such
as the tabulation approach or the binary search variant for the Lis question.
Now, if we go ahead with the tabulation approach, the time complexity will be of the order of n square.
For the same reason that we have discussed when we discuss the Lis question, and the space complexity
in the tabulation approach will be of the order of N, and therefore, if we solve this question using
the tabulation approach, the overall time complexity will be of the order of n square, because among
n square and n log n n square is bigger, and the overall space complexity will be of the order of n.
Now, if we solve this question using the binary search variant, the time complexity will be of the
order of n log n, and again you can refer the binary search variant video for the Lis question where
we have discussed this in detail.
And if we use this variant, the space complexity will be of the order of n okay.
So if we solve this question using the binary search variant, the overall time complexity will be n
log n, and the overall space complexity will be of the order of n.