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

2
00:00:01,220 --> 00:00:07,370
We have another interesting question over here which is called the Russian doll envelopes question.

3
00:00:07,370 --> 00:00:17,210
The question reads you are given a 2D array of integers envelopes where envelopes at position I is this

4
00:00:17,210 --> 00:00:18,110
element over here.

5
00:00:18,110 --> 00:00:24,290
Notice that each element in the envelopes array is an array in itself with two values.

6
00:00:24,290 --> 00:00:31,910
Okay, so w I is the width of the ith element and h I is the height of the ith element.

7
00:00:31,910 --> 00:00:41,030
Okay, so where envelopes at index I represents the width and height of an envelope, one envelope can

8
00:00:41,030 --> 00:00:49,370
fit into another if and only if both the width and height of one envelope are greater than the other

9
00:00:49,370 --> 00:00:49,940
envelopes.

10
00:00:49,940 --> 00:00:51,260
Width and height.

11
00:00:51,500 --> 00:00:54,830
Return the maximum number of envelopes you can.

12
00:00:54,830 --> 00:00:58,220
Russian doll that is put one inside the other.

13
00:00:58,220 --> 00:01:01,490
Note you cannot rotate an envelope.

14
00:01:01,490 --> 00:01:03,170
So this is the question over here.

15
00:01:03,170 --> 00:01:11,720
It says that you can fit one envelope into another only if the width and height is strictly lesser than

16
00:01:11,720 --> 00:01:13,640
the width and height of the other envelope.

17
00:01:13,640 --> 00:01:21,200
For example, over here we have this envelope, and from this image it's clear that the width over here

18
00:01:21,200 --> 00:01:26,810
is less than the width of this envelope, as well as the height of this envelope is less than the height

19
00:01:26,810 --> 00:01:27,800
of this envelope.

20
00:01:27,800 --> 00:01:33,230
So as per the condition mentioned over here, we will be able to put this envelope inside it.

21
00:01:33,230 --> 00:01:33,560
Okay.

22
00:01:33,560 --> 00:01:36,230
So we have this envelope over here.

23
00:01:36,230 --> 00:01:38,810
And outside this envelope we have the bigger one.

24
00:01:38,810 --> 00:01:42,380
So this process is what we call Russian doll okay.

25
00:01:42,380 --> 00:01:43,910
So that's the question over here.

26
00:01:43,910 --> 00:01:46,760
And then we are also given an example.

27
00:01:46,760 --> 00:01:52,880
And the question asks us to find the maximum number of envelopes that we can Russian doll.

28
00:01:52,880 --> 00:01:57,950
So in this example which is given to us notice we have one comma two.

29
00:01:57,950 --> 00:01:59,600
And then we have four comma three.

30
00:01:59,600 --> 00:02:01,370
And then we have five comma six okay.

31
00:02:01,370 --> 00:02:03,290
So this is the array which is given to us.

32
00:02:03,290 --> 00:02:10,430
But among these four envelopes which are there in this array we are able to Russian doll three envelopes

33
00:02:10,430 --> 00:02:11,420
in this manner.

34
00:02:11,420 --> 00:02:14,750
So this would be the envelope in the deepest layer.

35
00:02:14,750 --> 00:02:17,240
And above it we have this envelope.

36
00:02:17,240 --> 00:02:20,840
And on the outside we have this envelope over here.

37
00:02:20,840 --> 00:02:24,560
And again notice one is less than four and two is less than three.

38
00:02:24,560 --> 00:02:28,910
Similarly four is less than five and three is less than six.

39
00:02:28,910 --> 00:02:32,090
So the condition mentioned over here is satisfied.

40
00:02:32,120 --> 00:02:38,960
Now again remember the question also says that you cannot rotate an envelope, which means that you

41
00:02:38,960 --> 00:02:45,770
cannot interchange the width and height so as to be able to insert one envelope into another.

42
00:02:45,770 --> 00:02:51,800
Now, if you could rotate an envelope, this question would be pretty similar to another famous coding

43
00:02:51,800 --> 00:02:55,700
interview question, which is called the box stacking problem.

44
00:02:55,700 --> 00:02:58,490
Okay, but that's not the case over here.

45
00:02:58,490 --> 00:02:59,180
All right.

46
00:02:59,180 --> 00:03:05,420
So we have understood the question and we also have taken a look at the example which is given to us.

47
00:03:05,420 --> 00:03:12,350
Now remember it's very important that you ask any clarifying questions which you may want to ask.

48
00:03:12,350 --> 00:03:18,350
Now one question you could ask is if an empty array is given, does the output have to be zero?

49
00:03:18,350 --> 00:03:23,000
And let's say the interviewer replies, you will not be given an empty array.

50
00:03:23,000 --> 00:03:25,670
Okay, so there will be at least one envelope.

51
00:03:25,670 --> 00:03:29,570
You could also ask, or maybe you could just clarify that.

52
00:03:29,570 --> 00:03:32,780
What if two envelopes are of the same size?

53
00:03:32,780 --> 00:03:38,780
My understanding is that I will not be able to insert this envelope into another envelope, which has

54
00:03:38,780 --> 00:03:41,480
the same size as this envelope over here.

55
00:03:41,480 --> 00:03:45,680
And let's say the interviewer says, yes, your understanding is correct.

56
00:03:45,680 --> 00:03:52,460
So we have understood the question, and we have also asked any clarifying questions which we wanted

57
00:03:52,460 --> 00:03:53,240
to ask.

58
00:03:53,240 --> 00:03:56,570
Let's now proceed and try to solve this question.

59
00:03:56,570 --> 00:04:03,680
The first thing that we need to do is we need to be able to identify what pattern of question this is.

60
00:04:03,680 --> 00:04:10,040
Let's try to see whether there are any hints in the question which is given to us, which we can use

61
00:04:10,040 --> 00:04:14,420
to identify this first as a dynamic programming question.

62
00:04:14,720 --> 00:04:20,180
Notice over here it says return the maximum number of envelopes.

63
00:04:20,180 --> 00:04:20,630
Okay.

64
00:04:20,630 --> 00:04:28,040
So this means that we are asked to find an optimal solution, which is a strong hint that probably we

65
00:04:28,040 --> 00:04:31,100
could use dynamic programming to solve this question.

66
00:04:31,100 --> 00:04:34,820
We also have choices in this question okay.

67
00:04:34,820 --> 00:04:41,660
We could either include or pick a particular envelope, or we can just not pick it or exclude it.

68
00:04:41,660 --> 00:04:42,950
So we have choices.

69
00:04:42,950 --> 00:04:46,790
And we are also asked to find the optimal solution.

70
00:04:46,790 --> 00:04:51,260
So these are two powerful hints which we can use to identify that.

71
00:04:51,260 --> 00:04:54,110
This in fact is a dynamic programming question.

72
00:04:54,110 --> 00:04:59,720
And maybe it's a variation of the longest increasing subsequence question.

73
00:04:59,890 --> 00:05:07,870
Pattern, because we need to identify a sequence of envelopes such that one envelope is in another envelope.

74
00:05:07,870 --> 00:05:14,140
Now let's discuss more of this in the next video, where we will be brainstorming the approach that

75
00:05:14,140 --> 00:05:16,120
we can take to solve this question.