1
00:00:00,170 --> 00:00:02,030
Hey there and welcome back.

2
00:00:02,060 --> 00:00:09,800
Let's now get started with the very famous coding interview question called the Longest Increasing Subsequence.

3
00:00:09,830 --> 00:00:14,270
So the question reads given an integer array Numb's.

4
00:00:14,900 --> 00:00:22,670
Return the length of the longest strictly increasing subsequence, and we are given an example.

5
00:00:22,670 --> 00:00:25,160
Let's say this is the array which is given to us.

6
00:00:25,160 --> 00:00:29,570
So notice over here 12345.

7
00:00:29,570 --> 00:00:32,330
So this is a subsequence of this array.

8
00:00:32,330 --> 00:00:37,280
And it's in fact the longest strictly increasing subsequence.

9
00:00:37,280 --> 00:00:42,290
And therefore the required output for this input is equal to five.

10
00:00:42,290 --> 00:00:43,730
So this is the question.

11
00:00:43,730 --> 00:00:51,890
Now it's very important that you understand the difference between subsequence and substring or subarray.

12
00:00:52,280 --> 00:00:58,790
So if this is the array which is given to us for example, this part over here would be a substring

13
00:00:58,790 --> 00:01:00,020
or a subarray.

14
00:01:00,020 --> 00:01:02,900
Notice that nothing has been left in between.

15
00:01:02,900 --> 00:01:09,050
Now if you want to delete this element and just take these two elements, it's not a substring or a

16
00:01:09,080 --> 00:01:11,810
subarray, but rather it's a subsequence.

17
00:01:12,200 --> 00:01:17,270
So in this question we have to find the length of the longest increasing subsequence.

18
00:01:17,270 --> 00:01:22,460
Now that we have understood the question, remember, if you are presented with a coding interview question,

19
00:01:22,460 --> 00:01:28,460
it's very important that you ask any clarifying questions that you may want to ask.

20
00:01:28,460 --> 00:01:34,730
So a possible question for this question over here that you could ask is if an empty array is given,

21
00:01:34,730 --> 00:01:37,340
does the output have to be zero.

22
00:01:37,340 --> 00:01:41,150
And let's say the interviewer replies you won't be given an empty array.

23
00:01:41,330 --> 00:01:42,080
All right.

24
00:01:42,080 --> 00:01:46,820
Now if you have any other questions, make sure to ask them before you get started with solving the

25
00:01:46,820 --> 00:01:47,420
question.

26
00:01:48,040 --> 00:01:53,170
So we have understood the question and we have gone through any clarifying questions that we wanted

27
00:01:53,170 --> 00:01:53,920
to ask.

28
00:01:53,920 --> 00:01:56,680
Now let's go ahead and come up with a few test cases.

29
00:01:56,680 --> 00:02:01,210
And remember, you can come up with test cases together with your interviewer.

30
00:02:01,210 --> 00:02:05,920
And that's actually beneficial to ensure that both of you are on the same page.

31
00:02:05,920 --> 00:02:11,320
Now, we've already seen one test case, which was the example which was given to us.

32
00:02:11,320 --> 00:02:17,380
So if this is the input array, the longest increasing subsequence is of length five.

33
00:02:17,500 --> 00:02:23,680
Now, if you're given an array with just one element, then the output has to be equal to one because

34
00:02:23,680 --> 00:02:28,780
you just have one longest increasing subsequence which is this element itself.

35
00:02:28,810 --> 00:02:31,840
And let's say the array is 3 to 1.

36
00:02:32,020 --> 00:02:37,780
In this case, the output would again be one, because you can take either of these elements, but then

37
00:02:37,780 --> 00:02:43,540
you can't take any combination of elements such that the elements are strictly increasing.

38
00:02:43,540 --> 00:02:46,780
So over here also the output has to be equal to one.

39
00:02:47,140 --> 00:02:52,810
In the next video, let's try to think what approach can be taken for solving this question.