1
00:00:00,810 --> 00:00:01,950
Welcome back.

2
00:00:01,980 --> 00:00:09,000
So far we have discussed the recursive approach, the memoization approach, and the bottom up or tabulation

3
00:00:09,000 --> 00:00:09,570
approach.

4
00:00:09,570 --> 00:00:15,390
And we have also discussed the time and space complexity of all these three approaches.

5
00:00:15,420 --> 00:00:21,780
Notice that the space and time complexity of the tabulation and memoization approach are the same.

6
00:00:21,780 --> 00:00:27,030
So we have the space and time complexity of the order of N into M.

7
00:00:27,030 --> 00:00:30,990
But the bottom up approach is iterative in nature.

8
00:00:30,990 --> 00:00:34,800
So we will not be using space on the recursive call stack.

9
00:00:34,830 --> 00:00:39,360
Let's now implement the space optimized tabulation approach.

10
00:00:39,360 --> 00:00:45,960
So this is the table that we filled up when we discussed the tabulation or bottom up approach.

11
00:00:45,960 --> 00:00:49,530
For the example p q r s t and p r t.

12
00:00:49,800 --> 00:00:56,730
Now let's use this to come up with some interesting observations which we can use to optimize the solution

13
00:00:56,730 --> 00:00:58,380
that we had previously come up with.

14
00:00:58,410 --> 00:01:04,170
Notice that to fill any row, we only need the previous row.

15
00:01:04,170 --> 00:01:10,410
For example, when we were filling this row over here, we used either the diagonal value or the left

16
00:01:10,410 --> 00:01:12,330
value and the top value right.

17
00:01:12,330 --> 00:01:19,860
So to fill a current row, the row at hand, we only need the previous row and the current row itself.

18
00:01:19,860 --> 00:01:24,600
Over here we need the current row because in some cases we are using the left value as well.

19
00:01:24,600 --> 00:01:29,310
So there is no need to store this complete table over here.

20
00:01:29,310 --> 00:01:31,200
We could use two arrays.

21
00:01:31,200 --> 00:01:37,830
Let's say we have a previous array which for this example has four columns.

22
00:01:37,830 --> 00:01:43,620
And we have a current array which is again a 1D array with four cells.

23
00:01:43,620 --> 00:01:49,410
Now when we identify these values previous would have these values.

24
00:01:49,410 --> 00:01:53,790
And when we are done with filling these values we would allocate these values.

25
00:01:53,790 --> 00:01:57,480
Or we'll take a copy of this and assign it to the previous array.

26
00:01:57,480 --> 00:02:00,390
So this array over here this becomes previous.

27
00:02:00,870 --> 00:02:03,900
And this over here will become the current array.

28
00:02:03,990 --> 00:02:06,150
Again we calculate these values.

29
00:02:06,150 --> 00:02:10,380
And once we are done calculating these values we will make this previous.

30
00:02:11,180 --> 00:02:13,220
And this would become the current array.

31
00:02:13,250 --> 00:02:18,920
So in this manner notice that we just need these two one dimensional arrays.

32
00:02:18,920 --> 00:02:23,810
So the space complexity is going to be of the order of m.

33
00:02:23,810 --> 00:02:25,070
If this is M right.

34
00:02:25,070 --> 00:02:26,180
This is m columns.

35
00:02:26,180 --> 00:02:30,680
So that's why the space complexity is going to be of the order of M.

36
00:02:30,680 --> 00:02:38,750
So we have improved it from a space complexity of M into N to a space complexity of the order of M,

37
00:02:39,200 --> 00:02:41,900
where M is the number of columns.

38
00:02:41,900 --> 00:02:49,010
Now, to write this in an even better manner, you could try to identify which among n which was the

39
00:02:49,010 --> 00:02:55,430
number of rows over here, or the length of this string, so you could identify which among n and m

40
00:02:55,430 --> 00:02:56,630
is smaller.

41
00:02:56,630 --> 00:03:04,190
And by keeping that as the number of columns over here, you can achieve a space complexity of the order

42
00:03:04,190 --> 00:03:07,100
of the minimum between n and m.

43
00:03:07,100 --> 00:03:09,050
So this is the space complexity.

44
00:03:09,050 --> 00:03:15,200
And the time complexity is still going to be of the order of M into n, because we have to go through

45
00:03:15,200 --> 00:03:19,520
all these cells over here to find the answer, which we get over here.

46
00:03:19,520 --> 00:03:26,420
So this is the space optimized tabulation approach where instead of a 2D array we will just use two

47
00:03:26,420 --> 00:03:27,560
1D arrays.

48
00:03:27,650 --> 00:03:35,270
So we have discussed the four approaches for solving the LCS question and for the space optimized tabulation

49
00:03:35,270 --> 00:03:35,870
approach.

50
00:03:35,870 --> 00:03:42,920
The time complexity again was of the order of N into M, but the space complexity was of the order of

51
00:03:42,920 --> 00:03:45,470
the minimum between M and N.

52
00:03:45,470 --> 00:03:52,490
And notice that this space complexity is even better than the space complexity which we had over here.

53
00:03:52,490 --> 00:03:56,390
And the time complexity is definitely better than what we have over here.

54
00:03:56,390 --> 00:04:01,490
And the time complexity is the same as the memoization and bottom up approaches.