1
00:00:00,080 --> 00:00:06,200
Let's now write the space optimized tabulation approach for calculating fib of n.

2
00:00:06,230 --> 00:00:06,680
Okay.

3
00:00:06,680 --> 00:00:13,820
So let's get into it now initially itself, if n is less than or equal to one, we can just return n

4
00:00:13,820 --> 00:00:14,390
itself.

5
00:00:14,390 --> 00:00:21,140
So that would be pretty straightforward because we know that for n equal to zero, fib of zero is zero

6
00:00:21,140 --> 00:00:25,310
itself, and for n is equal to one, fib of one is one itself.

7
00:00:25,310 --> 00:00:30,770
Now, if that is not the case, as we have discussed in the previous video, we will need a few variables

8
00:00:30,770 --> 00:00:31,280
pref.

9
00:00:31,280 --> 00:00:32,270
Let's call it pref.

10
00:00:32,270 --> 00:00:34,520
So prev would be equal to zero at this point.

11
00:00:34,520 --> 00:00:41,510
And then we have cur for current and cur would be equal to one because zero and one are the first two

12
00:00:41,510 --> 00:00:42,650
Fibonacci numbers.

13
00:00:42,650 --> 00:00:44,750
And then we will also need a counter.

14
00:00:45,050 --> 00:00:52,610
And initially counter can be set to one, because we know the values in the Fibonacci series up to n

15
00:00:52,610 --> 00:00:53,990
is equal to one, right?

16
00:00:53,990 --> 00:00:56,660
We know fib of zero and we know fib of one.

17
00:00:56,660 --> 00:00:59,000
And that's why cur at this point is equal to one.

18
00:00:59,000 --> 00:01:01,520
And the counter is also set to one.

19
00:01:01,520 --> 00:01:08,660
Now we will need a while loop, and while counter less than n, it will keep going.

20
00:01:08,660 --> 00:01:15,170
And when the counter becomes equal to n, it would mean that we have already calculated fib of n, and

21
00:01:15,170 --> 00:01:20,600
that is why we come out of the while loop, and then we will just return whatever we are going to calculate.

22
00:01:20,600 --> 00:01:22,430
So let me keep this blank for now.

23
00:01:22,430 --> 00:01:30,710
So inside the while function we will calculate the next value in the Fibonacci expression or series

24
00:01:30,710 --> 00:01:32,510
using the previous two values.

25
00:01:32,510 --> 00:01:34,400
So I can say let.

26
00:01:34,400 --> 00:01:41,150
Next is equal to prev plus curve okay.

27
00:01:41,150 --> 00:01:48,740
And then because we have calculated the next value in the Fibonacci expression let me increment the

28
00:01:48,740 --> 00:01:49,250
counter.

29
00:01:49,250 --> 00:01:51,590
So counter plus is equal to one.

30
00:01:51,590 --> 00:01:55,940
And then we move the prev and curr values by one step.

31
00:01:55,940 --> 00:02:03,500
Because again we only need the latest two values to calculate the next value in the Fibonacci expression.

32
00:02:03,500 --> 00:02:08,840
So I say prev is equal to cur and we can say cur is equal to next.

33
00:02:08,840 --> 00:02:09,470
Okay.

34
00:02:09,470 --> 00:02:11,060
And then we proceed again.

35
00:02:11,060 --> 00:02:14,180
If counter is less than n we calculate the next value.

36
00:02:14,180 --> 00:02:18,650
We increment the counter and we shift prev and curr by one position.

37
00:02:18,650 --> 00:02:20,150
And we keep doing this.

38
00:02:20,150 --> 00:02:24,980
And once counter becomes equal to n we will come out of this while loop.

39
00:02:24,980 --> 00:02:26,690
And then we are over here.

40
00:02:26,690 --> 00:02:29,600
And cur has the value of next.

41
00:02:29,600 --> 00:02:34,610
So we will not be able to return next over here because next is defined inside the while loop.

42
00:02:34,610 --> 00:02:36,890
So you cannot return next over here.

43
00:02:36,890 --> 00:02:42,260
But that's not a problem because we are assigning the value of next to cur and we can just return cur

44
00:02:42,260 --> 00:02:42,650
over here.

45
00:02:42,650 --> 00:02:47,180
So cur would have the value of fib of n and we are returning that.

46
00:02:47,180 --> 00:02:50,960
Now let's go ahead and run this code and see if it's passing all the test cases.

47
00:02:51,680 --> 00:02:54,560
And you can see that it's passing all the test cases.