Welcome back.
In this video, let's try to build the intuition behind this approach for solving the Elias question,
where we will be using the binary search as well.
Now for this, let's take an example.
Let's say the array which is given to us is nine, two, seven, three, four and ten.
Now we will use a pointer to initially point at this index.
And with this pointer we will go through all the elements in the array which is given to us.
So initially the pointer is pointing at index zero.
And the value over here is nine.
Now we have to make a choice whether we can include this element in the subsequence that we are building,
which has to be strictly increasing because as of now, we have not included any element, and because
this is the first element in the array which is given to us, let's include this in the increasing subsequence.
So we have added nine over here.
And then we move this pointer ahead.
So now the pointer is pointing at the value two because that's index one.
Now there are two possibilities.
One possibility is that this value over here is greater than nine.
In which case we could just add it over here because this would still be increasing in nature.
But over here, because two is not greater than nine, we can't directly add two over here because nine
comma two is not an increasing subsequence.
So what do we do in this approach?
What we have to do is between 9 and 2.
What do you think would be better to keep in the increasing subsequence that we are building?
It would be logical to keep two rather than nine, because two is less than nine, and because two is
less than nine.
Probably if we have just two over here instead of nine, we are more likely to get elements over here
which are greater than two compared to nine, right?
For example, you get a three.
If you had kept nine, you couldn't add three.
But if you keep two over here instead of nine, you can add the three because three is greater than
two.
So instead of nine over here, let's replace this with a two.
And then we proceed to the next element.
So the next value over here is seven.
And seven is greater than two.
So let's add it to the subsequence that we are building which is increasing in nature.
Let's proceed to the next element and we have the value three over here.
And you see that three is not greater than seven.
All right.
So we can't add three over here because 273 is not strictly increasing.
So we have to decide whether to keep three or whether to keep seven over here.
Notice that between 3 and 7 it's better to keep three because three is less than seven.
So let's replace seven with three.
And we have three over here.
And we move the pointer ahead.
Now it is pointing at the value four and four is greater than three.
So we can add it over here.
And then again we move this forward.
And we have ten.
Now ten is greater than four.
So we can add it to the subsequence that we are building which is increasing in nature.
So we have reached the last element of the array which is given to us.
And we have identified that the length of the longest increasing subsequence is equal to four.
Now, always.
This may not give you a subsequence which is part of the array which is given to us, but we will discuss
more of that in the next video.
Over here we have discussed the general approach to build the intuition, and the general approach that
we will take in this approach is to iterate over all the values of the array which is given to us,
and if an element that we are considering is greater than the last element included in the increasing
subsequence, we will add that element as well to the increasing subsequence.
But if that is not the case, then we will have to find the smallest element which was already included
in the subsequence, which is greater than or equal to the new element.
And then we replace this element over here with the new element.
Because the new element is less than this element over here.
Now again, in the example that we had discussed, this becomes more clear.
So at one point we had two and seven in the subsequence and we were considering three.
And because three is not greater than seven, we cannot add it to the subsequence.
And in this approach we had to replace this seven over here with three.
Now, because we were just building the intuition, I took an example over here where we did not have
to search through this subsequence over here to identify which element had to be replaced with three.
We will discuss that in the next video.
But over here, remember you will see that the ideal element to be replaced is the smallest element
which was included.
That's greater than the three over here.
So for example, if we had two, four and seven and let's say we were considering whether we can include
the element three or not, now the smallest included element which is greater than three in this case
would be four.
And we would have to replace this element over here with three.
But more of that in the next video.