1
00:00:00,170 --> 00:00:01,190
Welcome back.

2
00:00:01,190 --> 00:00:05,090
Let's now get into the code for solving the Russian doll envelopes.

3
00:00:05,090 --> 00:00:05,720
Question.

4
00:00:05,720 --> 00:00:09,290
As we have discussed in the previous video, it's pretty straightforward.

5
00:00:09,290 --> 00:00:16,790
We just need to sort the envelopes given to us and then apply the Lis algorithm on the second element.

6
00:00:16,790 --> 00:00:17,150
Okay.

7
00:00:17,150 --> 00:00:18,290
So let's get started.

8
00:00:18,290 --> 00:00:25,430
So we're going to sort the envelopes array by width in ascending order and by height in descending order

9
00:00:25,430 --> 00:00:28,190
if the widths are the same okay.

10
00:00:28,190 --> 00:00:29,300
So let's do that.

11
00:00:39,380 --> 00:00:44,570
Okay, now let's say n is the length of the envelopes array.

12
00:00:46,670 --> 00:00:53,840
And let's create a DP array which will have the same size as the envelopes array which is given to us.

13
00:00:54,920 --> 00:00:59,180
And we are going to fill every cell in this DP with the value one.

14
00:00:59,180 --> 00:01:04,700
And we'll also need a max variable to track the longest increasing subsequence.

15
00:01:04,700 --> 00:01:06,950
And finally we will be returning this.

16
00:01:07,870 --> 00:01:08,230
All right.

17
00:01:08,230 --> 00:01:10,030
So this is the approach that we are taking.

18
00:01:10,030 --> 00:01:15,520
And all that remains is to apply the NIST algorithm on the second element.

19
00:01:15,520 --> 00:01:16,000
Okay.

20
00:01:16,000 --> 00:01:19,390
Again the envelopes array has arrays as elements.

21
00:01:19,390 --> 00:01:26,740
And in each element array we will just be taking a look at the second element to apply the Liz algorithm.

22
00:01:26,740 --> 00:01:39,790
So I can say for let I is equal to one I less than n I plus plus for let j is equal to zero j less than

23
00:01:39,790 --> 00:01:47,290
I, because j has to take the values from zero up to I minus one for a value of I okay and j plus plus.

24
00:01:48,400 --> 00:01:56,020
And now we are going to see whether envelopes at index I at index one, because we are taking a look

25
00:01:56,020 --> 00:02:03,670
at the second element in this particular array is greater than envelopes at index j at one okay.

26
00:02:03,670 --> 00:02:10,210
And if this is the case then we will check whether depee at J plus one is greater than DP at I.

27
00:02:10,720 --> 00:02:17,650
And if both of these are true then we will say dp at I is equal to tp at j plus one.

28
00:02:17,650 --> 00:02:22,000
Notice this is exactly the nice algorithm implemented, right?

29
00:02:22,000 --> 00:02:27,310
This is what we have discussed when we discuss the 1D tabulation approach for the nice question.

30
00:02:27,310 --> 00:02:31,720
Now, after we are through and after we have identified DP at I.

31
00:02:31,750 --> 00:02:37,780
Okay, so after we have gone through all the possible J's for a value of I, we have to check whether

32
00:02:37,780 --> 00:02:44,650
DP at I is greater than max, because if that is the case, then over here we can just assign max to

33
00:02:44,650 --> 00:02:46,090
be equal to dp at I.

34
00:02:46,090 --> 00:02:52,060
And this helps us to identify the maximum value in the DP array without having to iterate through it

35
00:02:52,060 --> 00:02:52,810
one more time.

36
00:02:52,810 --> 00:02:53,290
Okay.

37
00:02:53,290 --> 00:02:56,590
And then we are just returning Max over here and that's it.

38
00:02:56,590 --> 00:02:57,910
This should solve the question.

39
00:02:57,910 --> 00:03:02,320
Now let's go ahead and run this code and see if it's passing all the test cases.

40
00:03:04,060 --> 00:03:05,770
And you can see that it's working.

41
00:03:05,770 --> 00:03:08,050
It's passing all the test cases.

42
00:03:08,050 --> 00:03:13,840
Now also do try to implement the binary search variant of Lis in this question.

43
00:03:13,840 --> 00:03:18,730
That would be a great practice and I will provide the code for that as an article.