In the previous video, we have discussed the tabulation or bottom up approach for solving the Fibonacci
question.
Now over here, let's get started with the space optimized bottom up or tabulation approach.
Now, the way that we previously discussed the tabulation approach was that we would have a 1D table
like this.
And then we would just iterate from 2 to 5 to find the value of f of five.
But when we were filling this table over here, notice that at every point we only needed the previous
two values, and there was no need for storing all the values over here.
For example, for finding this value, we just need the previous two values.
Now for finding this value, we just need these two values.
There is no need of storing this value over here in a similar manner.
To find this value we just need these two values over here.
There's no need to store this value over here.
Now let's use this insight to come up with the space optimized bottom up or tabulation approach.
Now we know that the first two values in the Fibonacci series are zero and one.
And let's say again we want to find f of five.
So let's use two variables.
And we'll call the first value over here prev and the second one curve.
So this is for previous and this is for current.
So prev and curve.
Now let me just write the indices from 0 to 5 because we want to find f of five.
Now we also need a count variable to indicate till what time we need to keep moving these two variables
forward.
Because as we have just seen, we just need the previous two values at any point.
We don't need to store all the values from 0 to 5 for finding f of five.
Now, if the question asked us to find the Fibonacci number where n is either 0 or 1, then we would
already have our answer, because we know that when n is equal to zero, the value is zero, and when
n is equal to one, the value is one.
Now, if this is not the case and over here notice count is already one, which is this one over here.
Now if n is not 0 or 1 we'll have a while loop.
And it will say while count less than n, and then we'll keep moving these forward till we reach count
is equal to n, at which point we would break out of this loop.
So while count less than n, we can find the next value by just adding prev and curr.
So this is curr.
So we just need to add these two values to find the next value.
Now let me make some space over here and over here.
Notice that initially prev is zero and curr is one.
So next would be zero plus one which is equal to one.
So this is next over here which is equal to one.
That's what we found over here.
And then we would just move these two pointers forward.
So prev would come over here.
And curr would become this value over here.
So let's just move them.
And we have prev equal to one, and cur is equal to this one over here.
And we just need to increment our count.
So count now is equal to two.
And two is still less than five.
So we proceed and we again move prev and curr and we calculate the next value right.
So again let's continue this.
So at this point next would be the sum of these two values because prev is one and cur is one.
So next is equal to one plus one which is equal to two and count is equal to three.
And we move prev and car.
All right.
And again we see that three is less than five.
So we calculate the next value which is one plus two which is equal to three.
And we increment count and we move these two forward.
So prev is over here and car is over here.
And count which is four is still less than five.
So again we calculate next which is two plus three.
That's equal to five.
And we move prev and curr and we increment count.
So count becomes five.
And at this point we see that count is no longer less than n because n was five.
Because we are trying to find f of five.
And we come out of the loop.
And then you just need to either return curr or next.
It depends on how you write the code, but you just need to return this value over here.
So that gives us the answer.
So in this way, notice that at any point we are just having three variables prev, cur, and next.
And we don't need to store all the values from 0 to 5.
So even if we want to find f of 100, we would still just need these three variables which are prev
cur and next.
So that's why we've been able to optimize the space used for this solution.
Now the time complexity is still O of n, because we have to iterate from 2 to 5 to find f of five.
So we are doing almost n operations to find n Fibonacci numbers.
So to find f of five we have to find f of two, f of three, f of four.
And then we find f of five.
So the time complexity is of the order of n, and the space complexity is of the order of one or.
This solution runs in constant space because we are just using three variables cur, prev and next.
So we can say we're using three variables cur, prev and next.
So that's why the space complexity is of the order of one.
And notice that we've optimized the space usage.