1
00:00:00,170 --> 00:00:04,520
In the previous video, we have understood the Russian doll question.

2
00:00:04,520 --> 00:00:08,330
Now let's try to brainstorm how we can solve this question.

3
00:00:08,330 --> 00:00:10,670
So for this, let's take an example.

4
00:00:10,670 --> 00:00:13,250
Let's say this is the array which is given to us.

5
00:00:13,250 --> 00:00:20,420
And finally we'll have to identify this sequence because again this is the maximum number of envelopes

6
00:00:20,420 --> 00:00:25,850
you can select such that you are able to put one envelope in another envelope okay.

7
00:00:25,850 --> 00:00:32,780
So the criteria is that if we want to be able to put one envelope into another, then the width and

8
00:00:32,780 --> 00:00:39,650
height of the first envelope has to be lesser than the width and the height of the other envelope.

9
00:00:39,650 --> 00:00:40,310
Okay.

10
00:00:40,310 --> 00:00:48,410
So now let's see how we can solve this question just by sorting the envelopes which are given to us,

11
00:00:48,410 --> 00:00:51,740
and then by applying the alias algorithm.

12
00:00:51,740 --> 00:00:54,110
So let's take a look at that again.

13
00:00:54,110 --> 00:00:55,400
Let's use an example.

14
00:00:55,400 --> 00:00:58,370
So if this is the array which is given to us.

15
00:00:58,370 --> 00:01:02,450
And notice that every element in this array has two elements.

16
00:01:02,450 --> 00:01:06,200
So the first element represents the width of this particular envelope.

17
00:01:06,200 --> 00:01:11,360
And the second value over here represents the height of this particular envelope.

18
00:01:11,720 --> 00:01:20,930
Now if we go ahead and sort these envelopes by their first value which is two, seven, six and five,

19
00:01:20,930 --> 00:01:23,360
this is how the array would look like.

20
00:01:23,360 --> 00:01:24,560
So two comma three.

21
00:01:24,560 --> 00:01:28,730
And then you have five comma four six comma five and seven comma one.

22
00:01:28,730 --> 00:01:33,170
Notice that these values are now in increasing order.

23
00:01:33,200 --> 00:01:42,320
Now because these values are currently in increasing order, all that we need to do is to apply the

24
00:01:42,320 --> 00:01:47,330
alias algorithm on the second element in each of these.

25
00:01:47,330 --> 00:01:47,870
Okay.

26
00:01:47,870 --> 00:01:56,330
That is we are going to apply the alias algorithm thinking only of these values three, four, five

27
00:01:56,330 --> 00:01:57,230
and one.

28
00:01:57,230 --> 00:01:57,680
Okay.

29
00:01:57,680 --> 00:02:04,580
Now if I take these four values, notice that I am able to form an increasing sequence.

30
00:02:04,580 --> 00:02:07,700
If I were to just select these three okay.

31
00:02:07,700 --> 00:02:15,110
And when I just select these three automatically I am also considering their respective widths because

32
00:02:15,140 --> 00:02:16,460
again this is the width.

33
00:02:16,460 --> 00:02:21,470
This is the height right now because the widths are already in increasing order.

34
00:02:21,470 --> 00:02:28,010
If I can just select values that form an increasing sequence with respect to the heights, we already

35
00:02:28,010 --> 00:02:36,200
get three elements in a way that you are able to Russian doll them, and therefore the answer over here

36
00:02:36,200 --> 00:02:37,700
is equal to three.

37
00:02:37,700 --> 00:02:43,820
Okay, now again this is just the first part where we develop the intuition with respect to why this

38
00:02:43,820 --> 00:02:50,840
approach works, where we sort the envelopes and then apply the alias algorithm on the second element.

39
00:02:50,840 --> 00:02:55,070
But there are a few more nuances that we may need to consider.

40
00:02:55,310 --> 00:02:59,630
Now what if instead of five over here we had six?

41
00:02:59,630 --> 00:03:00,140
Okay.

42
00:03:00,140 --> 00:03:02,990
So this element is now six comma four.

43
00:03:02,990 --> 00:03:11,120
Now in this case if we sort it right we would still have the values in this order because these two

44
00:03:11,120 --> 00:03:13,130
values are just equal okay.

45
00:03:13,130 --> 00:03:15,920
So we have 266 and seven.

46
00:03:15,920 --> 00:03:18,830
And these values are sorted okay.

47
00:03:18,830 --> 00:03:23,480
So when we have six over here these are the elements in the envelopes array.

48
00:03:23,480 --> 00:03:25,820
And we have seen that they are already sorted.

49
00:03:25,820 --> 00:03:29,240
But then our algorithm in this case will not work.

50
00:03:29,240 --> 00:03:30,320
Why is that so.

51
00:03:30,320 --> 00:03:33,590
Because we have got it in this manner after sorting.

52
00:03:33,590 --> 00:03:41,330
And then when we try to apply alias on the second elements, okay, we think that we are getting three

53
00:03:41,330 --> 00:03:43,160
elements in increasing order.

54
00:03:43,160 --> 00:03:49,670
But the answer in this case is not three, because these two values are equal and therefore we are not

55
00:03:49,670 --> 00:03:53,060
able to insert one envelope in the other.

56
00:03:53,060 --> 00:03:57,740
Now, to solve this problem, we can approach it in two ways.

57
00:03:57,890 --> 00:04:05,090
The first method that we can use is before including an element in the longest increasing subsequence

58
00:04:05,090 --> 00:04:13,520
that we are forming, we will not only check the values at index one, which is the case as we saw over

59
00:04:13,520 --> 00:04:20,150
here, but rather we will check both the values at index one as well as at index zero.

60
00:04:20,150 --> 00:04:26,240
Okay, so in this case we would be able to see that these two are not increasing and therefore we will

61
00:04:26,240 --> 00:04:28,730
not include them in the Russian doll.

62
00:04:28,730 --> 00:04:31,040
So this is one way that we can solve this.

63
00:04:31,040 --> 00:04:38,120
And the second way is that if we find elements that are equal, when we are sorting the array which

64
00:04:38,120 --> 00:04:45,710
is given to us, we will sort those elements using the values at index one, which is this value and

65
00:04:45,710 --> 00:04:48,440
this value in descending order.

66
00:04:48,440 --> 00:04:48,950
Okay.

67
00:04:48,950 --> 00:04:53,480
So when we do that the array after sorting would look like this.

68
00:04:53,480 --> 00:04:57,470
Notice we have sorted these two values in descending order.

69
00:04:57,470 --> 00:04:59,270
So that's why we have five over here.

70
00:04:59,270 --> 00:04:59,870
And then.

71
00:05:00,050 --> 00:05:06,800
For over here, and then we would just need to apply the list algorithm on the second element, which

72
00:05:06,800 --> 00:05:10,130
is three, five, four and one.

73
00:05:10,130 --> 00:05:16,250
And when we do that, we get the answer as two, because we see that two is less than six and three

74
00:05:16,250 --> 00:05:17,270
is less than five.

75
00:05:17,270 --> 00:05:21,290
And we are able to Russian doll only these two envelopes.

76
00:05:21,290 --> 00:05:24,440
So these are the two ways that we can solve this question.

77
00:05:24,440 --> 00:05:30,530
And when we apply Liz, on the second element, we can use any of the methods that we have previously

78
00:05:30,530 --> 00:05:31,100
discussed.

79
00:05:31,100 --> 00:05:34,880
We can use the tabulation approach, the memoization approach.

80
00:05:34,880 --> 00:05:39,770
And we can also use the binary search variant of Liz okay.

81
00:05:39,770 --> 00:05:43,490
In fact, this variant will give us the best time complexity.