Welcome back.
So this is the tabulation approach that we had previously written for solving the LCS question.
Now let's go ahead and implement the space optimized tabulation approach.
Now as we have discussed in the previous video, we will not be needing a 2D array.
So let's remove this.
And instead we would need two 1D arrays, each of which is of length m plus one.
So let's go ahead and create them.
So let me call one prev for previous.
And this is going to equal array.
And the size of this is going to be m plus one.
And we will fill every cell in this array initially with the value zero.
And similarly we will need one more array.
So we call it curr.
And this also is going to equal array.
And the size is m plus one.
And we fill every cell in this array with the value zero.
All right.
Now we proceed.
We go ahead and iterate over the cells as we have over here.
And wherever.
Initially we had DP at I, we are going to replace this with curr.
And wherever we have DP at I minus one we are going to change this with prev.
So let's go ahead and do that.
So over here I have DP at I.
So let me replace this with curr.
And over here I have DP at I minus one.
So we write prev over here.
Similarly over here we have DP at I.
So let's write curr.
Over here we have DP at I over here.
So we can write curr over here.
And we have DP at I minus one over here.
So we write prev over here.
All right.
So that's it.
Now there's one more thing that we need to take care over here.
After each row computation or after each value of I is processed okay.
So once we come over here we have to make a copy of the current state of Curr.
And we have to assign it to prev okay.
And then it goes on to the next iteration okay.
So that's it.
And then finally over here we have DP at n and instead of DP at n we write curr.
We have to return curr at n.
So that's it.
So this should take care of this question.
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 way that we can solve the LCS question using the space optimized tabulation approach.