1
00:00:00,830 --> 00:00:07,550
In the previous video, we have discussed the tabulation or bottom up approach for solving the Fibonacci

2
00:00:07,550 --> 00:00:08,210
question.

3
00:00:08,210 --> 00:00:14,570
Now over here, let's get started with the space optimized bottom up or tabulation approach.

4
00:00:14,570 --> 00:00:20,240
Now, the way that we previously discussed the tabulation approach was that we would have a 1D table

5
00:00:20,240 --> 00:00:20,870
like this.

6
00:00:20,870 --> 00:00:25,940
And then we would just iterate from 2 to 5 to find the value of f of five.

7
00:00:25,940 --> 00:00:33,770
But when we were filling this table over here, notice that at every point we only needed the previous

8
00:00:33,770 --> 00:00:38,960
two values, and there was no need for storing all the values over here.

9
00:00:38,960 --> 00:00:43,640
For example, for finding this value, we just need the previous two values.

10
00:00:43,640 --> 00:00:48,080
Now for finding this value, we just need these two values.

11
00:00:48,080 --> 00:00:52,310
There is no need of storing this value over here in a similar manner.

12
00:00:52,310 --> 00:00:56,300
To find this value we just need these two values over here.

13
00:00:56,300 --> 00:00:58,880
There's no need to store this value over here.

14
00:00:58,880 --> 00:01:06,260
Now let's use this insight to come up with the space optimized bottom up or tabulation approach.

15
00:01:06,620 --> 00:01:13,190
Now we know that the first two values in the Fibonacci series are zero and one.

16
00:01:13,190 --> 00:01:16,520
And let's say again we want to find f of five.

17
00:01:16,850 --> 00:01:19,460
So let's use two variables.

18
00:01:19,460 --> 00:01:24,620
And we'll call the first value over here prev and the second one curve.

19
00:01:24,800 --> 00:01:27,200
So this is for previous and this is for current.

20
00:01:27,200 --> 00:01:28,550
So prev and curve.

21
00:01:28,640 --> 00:01:34,940
Now let me just write the indices from 0 to 5 because we want to find f of five.

22
00:01:34,970 --> 00:01:42,890
Now we also need a count variable to indicate till what time we need to keep moving these two variables

23
00:01:42,890 --> 00:01:43,580
forward.

24
00:01:43,580 --> 00:01:48,740
Because as we have just seen, we just need the previous two values at any point.

25
00:01:48,740 --> 00:01:54,350
We don't need to store all the values from 0 to 5 for finding f of five.

26
00:01:54,350 --> 00:02:02,660
Now, if the question asked us to find the Fibonacci number where n is either 0 or 1, then we would

27
00:02:02,660 --> 00:02:08,540
already have our answer, because we know that when n is equal to zero, the value is zero, and when

28
00:02:08,540 --> 00:02:10,490
n is equal to one, the value is one.

29
00:02:10,490 --> 00:02:16,880
Now, if this is not the case and over here notice count is already one, which is this one over here.

30
00:02:16,880 --> 00:02:21,770
Now if n is not 0 or 1 we'll have a while loop.

31
00:02:22,400 --> 00:02:30,050
And it will say while count less than n, and then we'll keep moving these forward till we reach count

32
00:02:30,050 --> 00:02:34,040
is equal to n, at which point we would break out of this loop.

33
00:02:34,040 --> 00:02:41,390
So while count less than n, we can find the next value by just adding prev and curr.

34
00:02:41,450 --> 00:02:42,560
So this is curr.

35
00:02:43,490 --> 00:02:47,690
So we just need to add these two values to find the next value.

36
00:02:47,720 --> 00:02:51,710
Now let me make some space over here and over here.

37
00:02:51,710 --> 00:02:55,490
Notice that initially prev is zero and curr is one.

38
00:02:55,490 --> 00:02:59,960
So next would be zero plus one which is equal to one.

39
00:02:59,960 --> 00:03:03,410
So this is next over here which is equal to one.

40
00:03:03,410 --> 00:03:04,910
That's what we found over here.

41
00:03:04,910 --> 00:03:08,810
And then we would just move these two pointers forward.

42
00:03:08,810 --> 00:03:10,940
So prev would come over here.

43
00:03:10,940 --> 00:03:13,370
And curr would become this value over here.

44
00:03:13,370 --> 00:03:14,750
So let's just move them.

45
00:03:16,250 --> 00:03:22,130
And we have prev equal to one, and cur is equal to this one over here.

46
00:03:22,250 --> 00:03:25,130
And we just need to increment our count.

47
00:03:25,130 --> 00:03:27,620
So count now is equal to two.

48
00:03:28,010 --> 00:03:30,230
And two is still less than five.

49
00:03:30,230 --> 00:03:36,890
So we proceed and we again move prev and curr and we calculate the next value right.

50
00:03:36,890 --> 00:03:38,330
So again let's continue this.

51
00:03:38,330 --> 00:03:44,180
So at this point next would be the sum of these two values because prev is one and cur is one.

52
00:03:44,180 --> 00:03:49,610
So next is equal to one plus one which is equal to two and count is equal to three.

53
00:03:49,610 --> 00:03:51,050
And we move prev and car.

54
00:03:54,280 --> 00:03:55,090
All right.

55
00:03:55,090 --> 00:03:58,870
And again we see that three is less than five.

56
00:03:58,870 --> 00:04:03,190
So we calculate the next value which is one plus two which is equal to three.

57
00:04:03,190 --> 00:04:06,550
And we increment count and we move these two forward.

58
00:04:08,350 --> 00:04:11,500
So prev is over here and car is over here.

59
00:04:11,500 --> 00:04:14,680
And count which is four is still less than five.

60
00:04:14,680 --> 00:04:17,680
So again we calculate next which is two plus three.

61
00:04:17,680 --> 00:04:19,240
That's equal to five.

62
00:04:19,240 --> 00:04:23,560
And we move prev and curr and we increment count.

63
00:04:23,560 --> 00:04:25,690
So count becomes five.

64
00:04:25,690 --> 00:04:31,870
And at this point we see that count is no longer less than n because n was five.

65
00:04:31,870 --> 00:04:33,820
Because we are trying to find f of five.

66
00:04:33,820 --> 00:04:35,650
And we come out of the loop.

67
00:04:35,650 --> 00:04:39,550
And then you just need to either return curr or next.

68
00:04:39,550 --> 00:04:43,840
It depends on how you write the code, but you just need to return this value over here.

69
00:04:44,140 --> 00:04:45,640
So that gives us the answer.

70
00:04:46,660 --> 00:04:54,220
So in this way, notice that at any point we are just having three variables prev, cur, and next.

71
00:04:54,220 --> 00:04:58,120
And we don't need to store all the values from 0 to 5.

72
00:04:58,120 --> 00:05:04,690
So even if we want to find f of 100, we would still just need these three variables which are prev

73
00:05:04,690 --> 00:05:06,070
cur and next.

74
00:05:06,070 --> 00:05:11,290
So that's why we've been able to optimize the space used for this solution.

75
00:05:11,290 --> 00:05:18,250
Now the time complexity is still O of n, because we have to iterate from 2 to 5 to find f of five.

76
00:05:18,250 --> 00:05:23,290
So we are doing almost n operations to find n Fibonacci numbers.

77
00:05:23,290 --> 00:05:28,480
So to find f of five we have to find f of two, f of three, f of four.

78
00:05:28,480 --> 00:05:30,250
And then we find f of five.

79
00:05:30,250 --> 00:05:37,930
So the time complexity is of the order of n, and the space complexity is of the order of one or.

80
00:05:37,930 --> 00:05:45,970
This solution runs in constant space because we are just using three variables cur, prev and next.

81
00:05:45,970 --> 00:05:49,750
So we can say we're using three variables cur, prev and next.

82
00:05:49,750 --> 00:05:53,770
So that's why the space complexity is of the order of one.

83
00:05:53,770 --> 00:05:57,490
And notice that we've optimized the space usage.