Welcome back.
So far we have discussed the recursive approach, the memoization approach, and the bottom up or tabulation
approach.
And we have also discussed the time and space complexity of all these three approaches.
Notice that the space and time complexity of the tabulation and memoization approach are the same.
So we have the space and time complexity of the order of N into M.
But the bottom up approach is iterative in nature.
So we will not be using space on the recursive call stack.
Let's now implement the space optimized tabulation approach.
So this is the table that we filled up when we discussed the tabulation or bottom up approach.
For the example p q r s t and p r t.
Now let's use this to come up with some interesting observations which we can use to optimize the solution
that we had previously come up with.
Notice that to fill any row, we only need the previous row.
For example, when we were filling this row over here, we used either the diagonal value or the left
value and the top value right.
So to fill a current row, the row at hand, we only need the previous row and the current row itself.
Over here we need the current row because in some cases we are using the left value as well.
So there is no need to store this complete table over here.
We could use two arrays.
Let's say we have a previous array which for this example has four columns.
And we have a current array which is again a 1D array with four cells.
Now when we identify these values previous would have these values.
And when we are done with filling these values we would allocate these values.
Or we'll take a copy of this and assign it to the previous array.
So this array over here this becomes previous.
And this over here will become the current array.
Again we calculate these values.
And once we are done calculating these values we will make this previous.
And this would become the current array.
So in this manner notice that we just need these two one dimensional arrays.
So the space complexity is going to be of the order of m.
If this is M right.
This is m columns.
So that's why the space complexity is going to be of the order of M.
So we have improved it from a space complexity of M into N to a space complexity of the order of M,
where M is the number of columns.
Now, to write this in an even better manner, you could try to identify which among n which was the
number of rows over here, or the length of this string, so you could identify which among n and m
is smaller.
And by keeping that as the number of columns over here, you can achieve a space complexity of the order
of the minimum between n and m.
So this is the space complexity.
And the time complexity is still going to be of the order of M into n, because we have to go through
all these cells over here to find the answer, which we get over here.
So this is the space optimized tabulation approach where instead of a 2D array we will just use two
1D arrays.
So we have discussed the four approaches for solving the LCS question and for the space optimized tabulation
approach.
The time complexity again was of the order of N into M, but the space complexity was of the order of
the minimum between M and N.
And notice that this space complexity is even better than the space complexity which we had over here.
And the time complexity is definitely better than what we have over here.
And the time complexity is the same as the memoization and bottom up approaches.