1
00:00:00,110 --> 00:00:00,980
Welcome back.

2
00:00:01,010 --> 00:00:06,500
Let's now get into the code for the binary search variant for solving the Liz question.

3
00:00:06,530 --> 00:00:11,690
Now, the way that we are going to implement this is that we are going to iterate over the elements

4
00:00:11,690 --> 00:00:14,060
of the Numb's array, which is given to us.

5
00:00:14,060 --> 00:00:20,960
And for each element, we will check whether the element at hand is greater than the last element in

6
00:00:20,960 --> 00:00:23,060
the subsequence that we are forming.

7
00:00:23,090 --> 00:00:27,710
Now, if that is the case, then we will just append that element to the subsequence.

8
00:00:27,710 --> 00:00:35,630
But if that is not the case, then we will insert that particular element into the subsequence at the

9
00:00:35,630 --> 00:00:42,050
position of the element in the subsequence, which is the least number which is greater than or equal

10
00:00:42,050 --> 00:00:44,210
to the number that we are considering.

11
00:00:44,210 --> 00:00:44,690
All right.

12
00:00:44,690 --> 00:00:45,980
So let's get into it.

13
00:00:46,010 --> 00:00:49,910
Now again just to start with let's quickly handle an edge case.

14
00:00:49,910 --> 00:00:52,730
So if we are just given an empty numb's array.

15
00:00:52,940 --> 00:00:59,180
So if numb's dot length is equal to zero then we will just return zero okay.

16
00:00:59,180 --> 00:01:03,710
Because the length of the longest increasing subsequence in this case is equal to zero.

17
00:01:03,740 --> 00:01:04,340
Okay.

18
00:01:04,340 --> 00:01:09,920
So with that out of the way, let's quickly first write the skeleton of the approach.

19
00:01:09,920 --> 00:01:12,320
And then we will go ahead and add the details.

20
00:01:12,320 --> 00:01:14,450
So we will need a function.

21
00:01:14,450 --> 00:01:21,080
Let's just call it binary search which will give us the index where we would have to insert the element

22
00:01:21,080 --> 00:01:22,910
at hand into the subsequence.

23
00:01:22,910 --> 00:01:28,430
And that's the case when the element at hand or the element that we are considering is not greater than

24
00:01:28,430 --> 00:01:31,100
the last element in the subsequence that we are forming.

25
00:01:31,100 --> 00:01:33,410
Okay, so const binary search.

26
00:01:33,410 --> 00:01:37,250
And to this function we will have to pass the subsequence that we are forming.

27
00:01:37,250 --> 00:01:43,880
And we will also have to pass the number for which we have to identify the place where we have to insert

28
00:01:43,880 --> 00:01:45,230
it to the subsequence.

29
00:01:45,260 --> 00:01:49,160
Now let's write the details of this function later okay.

30
00:01:49,160 --> 00:01:50,750
So let's keep it over here.

31
00:01:50,750 --> 00:01:55,160
And proceeding further, let's create an array over here for the subsequence.

32
00:01:55,160 --> 00:02:01,640
And to this array, let's fill the value in the numb's array at index zero okay.

33
00:02:01,640 --> 00:02:06,320
And now let's iterate through the remaining values in the nums array.

34
00:02:06,320 --> 00:02:08,450
So for that we'll just use a for loop.

35
00:02:08,450 --> 00:02:15,530
So for let I is equal to one I less than nums dot length I plus plus okay.

36
00:02:15,530 --> 00:02:19,700
And let's say num is equal to numb's at I.

37
00:02:19,730 --> 00:02:22,910
Just to improve the readability of the code that we are writing.

38
00:02:22,910 --> 00:02:29,750
Now, let's check whether num is greater than the last value that was added to the subsequence.

39
00:02:29,750 --> 00:02:36,440
So I can say if num greater than sub at index sub dot length minus one.

40
00:02:36,440 --> 00:02:39,860
Okay, now if that is the case then it's pretty straightforward.

41
00:02:39,860 --> 00:02:43,520
We will just push that particular number to the subsequence.

42
00:02:43,520 --> 00:02:47,450
So sub dot push num okay.

43
00:02:47,450 --> 00:02:49,670
Now if this is not the case.

44
00:02:50,620 --> 00:02:58,060
Then we would have to insert this particular number at the position of the element, which is the least

45
00:02:58,060 --> 00:03:02,890
number in the subsequence, which is greater than or equal to the number that we are considering.

46
00:03:02,890 --> 00:03:03,310
Okay.

47
00:03:03,310 --> 00:03:06,730
And we will get the index of this particular number.

48
00:03:06,730 --> 00:03:09,520
Using the binary search function that we have written.

49
00:03:09,520 --> 00:03:14,710
Again, we will write the details of that function soon, and we have discussed that to this function.

50
00:03:14,710 --> 00:03:20,260
The binary search function over here will have to pass sub and num okay.

51
00:03:20,260 --> 00:03:24,550
So we'll get back the index where this particular number has to be inserted.

52
00:03:24,550 --> 00:03:28,960
And then we will just say sub at index is equal to num.

53
00:03:30,010 --> 00:03:31,000
And that's it.

54
00:03:31,000 --> 00:03:38,080
And finally once we are out of this for loop we would just have to return the length of sub okay.

55
00:03:38,080 --> 00:03:39,550
So that would give us the answer.

56
00:03:39,550 --> 00:03:40,930
So let's just write that over here.

57
00:03:43,180 --> 00:03:43,780
All right.

58
00:03:44,590 --> 00:03:49,270
Now, all that remains is that we need to add the details for the binary search function.

59
00:03:49,270 --> 00:03:50,380
So let's do that.

60
00:03:50,380 --> 00:03:53,440
And for this we would need two pointers.

61
00:03:53,440 --> 00:03:55,660
Let's just call it left and right.

62
00:03:55,660 --> 00:03:57,880
And left would be equal to zero.

63
00:03:57,880 --> 00:04:03,280
And right would be equal to the last valid index in the subsequence at hand.

64
00:04:03,280 --> 00:04:03,730
Okay.

65
00:04:03,970 --> 00:04:06,040
Now we will have a while loop.

66
00:04:06,040 --> 00:04:11,710
And this will keep looping as long as left is less than right okay.

67
00:04:11,710 --> 00:04:14,620
And over here we will calculate the mid value.

68
00:04:14,620 --> 00:04:20,140
So let me say let mid is equal to math dot floor.

69
00:04:22,110 --> 00:04:25,380
Left plus right divided by two okay.

70
00:04:25,380 --> 00:04:28,890
And again we're doing this because we don't want the decimal value okay.

71
00:04:28,890 --> 00:04:35,550
And then we will be checking if sub hat mid is less than num okay.

72
00:04:35,550 --> 00:04:42,960
If that is the case then definitely we would not be inserting the number that we want to insert at the

73
00:04:42,960 --> 00:04:44,220
index mid right.

74
00:04:44,220 --> 00:04:48,450
And therefore we can say left is equal to mid plus one.

75
00:04:48,630 --> 00:04:56,520
But if that is not the case then we would say right is equal to mid because even mid could be one of

76
00:04:56,520 --> 00:04:59,850
the positions where we would want to insert that particular number.

77
00:04:59,850 --> 00:05:03,180
And then once we are out of this while loop, that would be the case.

78
00:05:03,180 --> 00:05:09,210
When left is no longer less than right, we can just return either left or right.

79
00:05:09,240 --> 00:05:11,610
Now let me just return left in this case.

80
00:05:11,790 --> 00:05:12,720
And that's it.

81
00:05:12,720 --> 00:05:14,280
Now this should solve the question.

82
00:05:14,280 --> 00:05:18,720
Now let's go ahead and run this code and see if it's passing all the test cases.

83
00:05:18,780 --> 00:05:20,640
And again I've noticed I have a typo over here.

84
00:05:20,640 --> 00:05:22,230
So let's correct that all right.

85
00:05:22,260 --> 00:05:25,770
Now let's go ahead and run this code and see if it's passing all the test cases.

86
00:05:26,730 --> 00:05:28,350
And you can see that it's working.

87
00:05:28,350 --> 00:05:30,060
It's passing all the test cases.

88
00:05:30,360 --> 00:05:34,380
So this is the binary search variant for solving the Lis question.