Welcome back.
Let's now get into the code for the binary search variant for solving the Liz question.
Now, the way that we are going to implement this is that we are going to iterate over the elements
of the Numb's array, which is given to us.
And for each element, we will check whether the element at hand is greater than the last element in
the subsequence that we are forming.
Now, if that is the case, then we will just append that element to the subsequence.
But if that is not the case, then we will insert that particular element into the subsequence at the
position of the element in the subsequence, which is the least number which is greater than or equal
to the number that we are considering.
All right.
So let's get into it.
Now again just to start with let's quickly handle an edge case.
So if we are just given an empty numb's array.
So if numb's dot length is equal to zero then we will just return zero okay.
Because the length of the longest increasing subsequence in this case is equal to zero.
Okay.
So with that out of the way, let's quickly first write the skeleton of the approach.
And then we will go ahead and add the details.
So we will need a function.
Let's just call it binary search which will give us the index where we would have to insert the element
at hand into the subsequence.
And that's the case when the element at hand or the element that we are considering is not greater than
the last element in the subsequence that we are forming.
Okay, so const binary search.
And to this function we will have to pass the subsequence that we are forming.
And we will also have to pass the number for which we have to identify the place where we have to insert
it to the subsequence.
Now let's write the details of this function later okay.
So let's keep it over here.
And proceeding further, let's create an array over here for the subsequence.
And to this array, let's fill the value in the numb's array at index zero okay.
And now let's iterate through the remaining values in the nums array.
So for that we'll just use a for loop.
So for let I is equal to one I less than nums dot length I plus plus okay.
And let's say num is equal to numb's at I.
Just to improve the readability of the code that we are writing.
Now, let's check whether num is greater than the last value that was added to the subsequence.
So I can say if num greater than sub at index sub dot length minus one.
Okay, now if that is the case then it's pretty straightforward.
We will just push that particular number to the subsequence.
So sub dot push num okay.
Now if this is not the case.
Then we would have to insert this particular number at the position of the element, which is the least
number in the subsequence, which is greater than or equal to the number that we are considering.
Okay.
And we will get the index of this particular number.
Using the binary search function that we have written.
Again, we will write the details of that function soon, and we have discussed that to this function.
The binary search function over here will have to pass sub and num okay.
So we'll get back the index where this particular number has to be inserted.
And then we will just say sub at index is equal to num.
And that's it.
And finally once we are out of this for loop we would just have to return the length of sub okay.
So that would give us the answer.
So let's just write that over here.
All right.
Now, all that remains is that we need to add the details for the binary search function.
So let's do that.
And for this we would need two pointers.
Let's just call it left and right.
And left would be equal to zero.
And right would be equal to the last valid index in the subsequence at hand.
Okay.
Now we will have a while loop.
And this will keep looping as long as left is less than right okay.
And over here we will calculate the mid value.
So let me say let mid is equal to math dot floor.
Left plus right divided by two okay.
And again we're doing this because we don't want the decimal value okay.
And then we will be checking if sub hat mid is less than num okay.
If that is the case then definitely we would not be inserting the number that we want to insert at the
index mid right.
And therefore we can say left is equal to mid plus one.
But if that is not the case then we would say right is equal to mid because even mid could be one of
the positions where we would want to insert that particular number.
And then once we are out of this while loop, that would be the case.
When left is no longer less than right, we can just return either left or right.
Now let me just return left in this case.
And that's it.
Now this should solve the question.
Now let's go ahead and run this code and see if it's passing all the test cases.
And again I've noticed I have a typo over here.
So let's correct that all right.
Now let's go ahead and run this code and see if it's passing all the test cases.
And you can see that it's working.
It's passing all the test cases.
So this is the binary search variant for solving the Lis question.