1
00:00:00,050 --> 00:00:05,960
Let's now discuss the space and time complexity of the approach that we have discussed in the previous

2
00:00:05,960 --> 00:00:06,500
video.

3
00:00:06,500 --> 00:00:08,930
So these are the two steps that we had.

4
00:00:08,930 --> 00:00:14,630
We first had to sort the envelopes and then we applied lis on the second element.

5
00:00:14,630 --> 00:00:15,050
Okay.

6
00:00:15,050 --> 00:00:21,050
Now sorting the envelopes will take up work of the order of n log n.

7
00:00:21,050 --> 00:00:27,470
And when it comes to space it will take up space either of the order of log n if you are using quicksort

8
00:00:27,470 --> 00:00:31,460
or even constant space if you are using something like heapsort.

9
00:00:31,460 --> 00:00:31,910
Okay.

10
00:00:31,910 --> 00:00:39,650
And the second step, which is to apply lis on the second element, can be done in multiple ways, such

11
00:00:39,650 --> 00:00:45,530
as the tabulation approach or the binary search variant for the Lis question.

12
00:00:45,530 --> 00:00:51,200
Now, if we go ahead with the tabulation approach, the time complexity will be of the order of n square.

13
00:00:51,200 --> 00:00:57,140
For the same reason that we have discussed when we discuss the Lis question, and the space complexity

14
00:00:57,140 --> 00:01:04,370
in the tabulation approach will be of the order of N, and therefore, if we solve this question using

15
00:01:04,370 --> 00:01:11,420
the tabulation approach, the overall time complexity will be of the order of n square, because among

16
00:01:11,420 --> 00:01:18,590
n square and n log n n square is bigger, and the overall space complexity will be of the order of n.

17
00:01:18,590 --> 00:01:24,530
Now, if we solve this question using the binary search variant, the time complexity will be of the

18
00:01:24,530 --> 00:01:32,420
order of n log n, and again you can refer the binary search variant video for the Lis question where

19
00:01:32,420 --> 00:01:34,070
we have discussed this in detail.

20
00:01:34,070 --> 00:01:40,400
And if we use this variant, the space complexity will be of the order of n okay.

21
00:01:40,460 --> 00:01:46,280
So if we solve this question using the binary search variant, the overall time complexity will be n

22
00:01:46,280 --> 00:01:51,680
log n, and the overall space complexity will be of the order of n.