Hey there and welcome back!
In the previous video, we have started to develop the intuition behind this approach for solving the
Liz question over here.
Let's start with thinking about two aspects.
First of all, let's try to think why this works.
This part over here where if we encounter an element which is not greater than the last included element,
why does replacing the smallest included element greater than the new element actually work?
So let's discuss this aspect.
Secondly, let's also discuss why in this approach, after we are done iterating through all the elements
in the array which is given to us, we may not get an actual increasing subsequence which is part of
this array, but we will still get the length.
And remember, the question only asks us to identify the length of the longest increasing subsequence.
So let's get started and discuss these two aspects of this approach.
So let's take another example over here.
Let's say the array which is given to me is two, three, four and one.
Now let's walk through the approach that we have discussed over here.
So initially we have two we included in the subsequence that we are building.
Now we move to the next element which is three.
Now three is greater than two.
So let's include it over here.
We move to the next element.
We get four.
Now four is greater than three.
So we include it over here.
Then we move to one.
Now one is not greater than four.
So we have to identify the smallest included element which is greater than equal to one.
So the smallest included element or the smallest value among these three values which is greater than
or equal to one is two.
And we replace two with one.
So notice that over here the increasing subsequence that we are getting is one, three, four, which
is not a subsequence of the array which is given to us.
Right.
So that's what I meant with point number two over here.
But that does not matter, because the length of this is still the length of the longest increasing
subsequence in the array which is given to us.
And that's all that we are asked to find.
So the length of the longest increasing subsequence over here is three.
And over here also notice that the length of the longest increasing subsequence is three.
So this approach actually works and helps us identify the length.
But then let's discuss more about the why now.
So why does this approach work now?
To discuss this aspect, let me take two examples.
So let's say the array which is given to us in example one is 910 and one.
And let's say in example two, the array which is given to us is nine, ten, one, two and three.
Now in the case of the first example, we would first add nine to the subsequence array that we are
building which is increasing in nature.
Then we come to the next element.
As ten is greater than nine, we can include it over here.
And then we come to the next element which is equal to one.
Now one is not greater than ten, so we can't place it over here.
And then we have to find the smallest included element which is greater than or equal to one.
And among nine and ten, the smallest included element greater than or equal to one is nine.
So we replace nine with one.
Now first of all, notice that we still do get the length of the longest increasing subsequence, because
when we included one over here, the length did not change.
When we just had nine and ten, the length of this subsequence was equal to two, and even after changing
9 to 1, the length over here is still two.
So the length of the subsequence that we are building only changes when we encounter an element which
is larger than the last included element.
So that's why this works.
And over here we still get the answer which is two.
That's the length over here.
And that is the length of the longest increasing subsequence over here.
Even though one comma ten is not a subsequence of this array over here.
Now let's take a look at the second example over here.
And let's build the solution.
So we start by including nine.
Then we proceed to the next element which is ten.
Ten is greater than this nine over here.
So we can include it.
And then we come to one.
Now one is not greater than ten.
So we replace and change this nine over here to one.
And then we come to the next element, which is two.
Now two is also not greater than ten.
So we have to identify the smallest included element which is greater than or equal to two.
So in this case that's going to be equal to ten because one is not greater than or equal to two.
So the smallest included element greater than or equal to two is this ten over here.
So we replace ten with two.
And now the subsequence over here is one comma two.
And then we come to the next element.
And three is greater than two.
So we can include it over here.
And notice that we get a subsequence over here of length three.
Now why was it needed to replace this nine over here with one?
Notice that to capture this subsequence, which is a possibility, we had to do this.
So even though doing this, if it was just over here, if the question was just this much, doing this
change did not change the length of the list, which in a way meant that it did not harm the solution,
but it was still necessary for the solution to capture this possibility over here.
So this is why this approach works.
Now let's quickly summarize what we have learned.
So let's say this is the array which is given to us.
So we build a subsequence by iterating over the elements in the array which is given to us.
And if we find an element which is larger than the last included element, we will append it or include
it to the subsequence.
And if that is not the case, then we will replace the smallest element which is greater than or equal
to the new element which was already included in the subsequence.
So this is the approach that we will take over here.
Now where does binary search come into play in this approach.
So it's going to come into play over here because we have to identify in the subsequence which is the
smallest element greater than or equal to the new element which is already included in the subsequence.
Now for this or to identify this element, we could do normal search which is going to be an O of n
operation.
Or we could do binary search, which is going to be an O of log n operation.
And because we have to do this for all elements, if we implement the normal search, the total time
complexity is going to be n into n.
But by implementing binary search, the total time complexity is just going to be n into log n.